백준 문제풀이 : (17386) 선분 교차 1, 두 직선의 기울기로 문제 풀기 - C/C++

문제 : https://www.acmicpc.net/problem/17386

17386번: 선분 교차 1

 

시간 제한	메모리 제한	난이도	알고리즘 분류
0.25초	512 MB	Gold 3	기하학 / 선분 교차 판정

 

 

문제

 

 

시간 제한이 0.25초이므로 사실 상 계산 공식을 통해 한 번에 답을 도출하라는 뜻이다. 

 

처음에는 풀이법이 금방 생각나서 이게 왜 골드 3 짜리 문제인지 의문이었지만, CCW 알고리즘을 사용하지 않고는 기울기를 구하는 과정에서 소수점 오차까지 고려해야하기 때문인 것 같았다. 

CCW 알고리즘을 사용하는 문제는 골드 5에도 한 문제 있었는데, 이 '선분 교차1' 문제는 CCW 알고리즘을 응용해서 풀어야 하는 문제이기에 골드 3 난이도를 받은 모양이다. 

 

우선 나는 CCW 알고리즘이 무엇인 지 모르는 상태에서 풀이를 시작했다. 알고리즘을 검색해볼까 싶었지만 어쩐지 지는 기분이라서(...) 끝까지 매달려봤다. 다행스럽게도 거의 포기하기 직전에 무사히 해결됐다.

 

CCW를 활용한 풀이법은 이미 구글링하면 많이 보이기 때문에, 이 글에서는 기울기를 활용한 풀이법만 정리해두기로 했다. (사실 오차범위 조절이 풀이의 9할이라서 정리해둘게 없긴 하다..)

 

 

풀이

우선 오차 범위 고려하지 않고 단순하게 해결법만 생각해본다. L1, L2 두 선분이 교차하는 경우와 교차하지 않는 경우의 조건은 아래와 같다.

 

<두 선이 교차하는 경우>

1. 두 선의 기울기가 다르다. (세 점이 일직선 위에 있는 TC는 없기 때문에 Y절편 값이 같은 경우는 고려하지 않아도 된다.)

2. 두 선의 접점이 두 선의 X값 범위 내에 있다. (혹은 Y값 범위 내에 있다.) 

3. (위 2번 조건을 사용하기 위해서는 x1<x2 혹은 y1<y2이어야 하고, x3<x4 혹은 y3<y4 이어야 한다.)

 

<두 선이 교차하지 않는 경우>

1. 두 선의 기울기가 같다.

2. 두 선의 접점이 두 선의 X값 범위 밖에 있다.  (혹은 Y값 범위 내에 있다.)

 

직선의 기울기를 구하는 공식은 직선의 양 끝이 (x1, y1)과 (x2, y2)일 경우, $$ \frac{y2-y1}{x2-x1}$$ 이다. 

 

직선의 기본 방정식은 " y=(기울기)x + (y절편) "이다. (기울기)를 위 공식으로 알아냈으므로, x와 y자리에 (x1, y1) 혹은 (x2, y2) 값을 대입해 (y절편)의 값도 구할 수 있다.

 

직선이 두 개이므로 방정식은 두 개 나올 수 있고, 두 방정식을 계산하면 두 직선이 겹치는 접점 n, m을 구할 수 있게 된다. 악필로 정리해보자는 다음과 같다. 

 

 

이후, 위 공식으로 구해진 n의 값이 두 직선의 x범위 사이에 있거나, m의 값이 두 직선의 y범위 사이에 있다면 두 선은 교차하고 있는 것이다. 

 

여기까지 정리가 됐으면, 이제 다소 골치 아플 수 있는 두 가지 애로사항을 고려해줘야 한다. 

 

1) 소수점 계산

위 공식을 수행하는 과정에서 나눗셈을 사용하므로 n과 m 값은 실수가 될 가능성이 있다. 따라서, 이 부분에서 오차 범위를 고려해줘야 한다.

 

실수 연산을 해야 하므로 테스트 케이스는 전부 double 값으로 받는다. 하지만 실수 연산은 '==' 비교 연산자를 사용할 수 없다. 오차 범위를 설정한 후 해당 오차 범위 내에 있는 경우에만 '두 값은 같다' 로 판정해야한다. 

 

2) 직선이 y축과 평행할 경우의 기울기 고려

직선이 x축과 평행할 경우 기울기 값은 0이다. 하지만 y축과 평행할 경우 기울기는 존재하지 않는게 되어, 수치화가 애매해진다. 하지만 직선 방정식의 해를 구하기 위해서는 무조건 기울기의 수치가 필요하다. 따라서 이 풀이에서는 최대한 y축 평행에 가까운 기울기 값을 줬다. 

 

x=1 일 경우의 기울기 최대값은 1,000,000이다. 하지만 x의 값은 1 이하의 소수점으로 줄어들 수도 있으므로, 최대값은 1,000,000에 10을 곱해나가는 수로 정해야 할 것이다. (x의 값이 0.1, 0.01, 0.001로 줄어들 수록 기울기의 값은 10의 배수 단위로 늘어날 것이기에...)

 

위 두 가지 애로사항의 값(오차 범위의 값, 기울기 최대값)을 다양하게 조절해가며 정답 제출을 시도해봤다. 그리고 nn번의 시도 끝에 모든 테스트케이스를 만족하는 값을 찾아냈다. 

 

 

코드 작성

#include <stdio.h>
#include <math.h>
#define swap(a, b) { int tmp=a; a=b; b=tmp; }
#define comp(a, b) ((fabs(a-b)<0.00000000001) ? true : false)
using namespace std;

int main() {
    double x1, y1, x2, y2, x3, y3, x4, y4;
    scanf("%lf %lf %lf %lf\n%lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);

    if (x1>x2) {
        swap(x1, x2);
        swap(y1, y2);
    }
    
    if (x3>x4) {
        swap(x3, x4);
        swap(y3, y4);
    } 
    //아래에서 x값의 범위를 판단해야하므로 x값이 더 작은 점을 (x1,y1) (x3,y3) 쌍으로 바꿔주기
        
    double slope1=0;
    if (comp(x2,x1)) slope1=1000000000000000000; 
    //기울기 값이 같다면(오차범위 내라면) 기울기 최대값 설정
    else slope1 = (y2-y1)/(x2-x1);

    double slope2=0;
    if (comp(x3, x4)) slope2=1000000000000000000;
    else slope2 = (y4-y3)/(x4-x3);
    
    double flat_1 = y1 - (slope1*x1);  
    double flat_2 = y3 - (slope2*x3);
    //각 방정식의 y절편 구하기
    
    double n = (flat_2-flat_1)/(slope1-slope2);
    double m = slope1*n+flat_1;
    //두 방정식의 해 (n, m) 구하기
    
    if (comp(slope1, slope2)) printf("0");  
    //기울기가 같다면(오차범위 내라면) 두 직선은 평행하므로, 0 출력
    else {
        if ( ((x1<=n&&n<=x2) || comp(x1, n) || comp(x2,n) ) && ((x3<=n&&n<=x4) || comp(x3, n) || comp(x4,n) ) ) printf("1");
        //n(해의 x값)이 두 직선의 x범위 내에 있다면 1 출력. 
        //다만, x1==n의 비교연산은 정확하지 않을 수 있으므로 comp(x1, n)으로 대체해줌
        else printf("0");
    } 
    
    return 0;
}

 

위 코드에 적힌대로 오차범위를 '0.00000000001' 으로, 최대 기울기를 '1,000,000,000,000,000,000' 으로 설정하니 모든 TC를 통과했다. 

 

후기. 역시 알고리즘은 괜히 있는게 아닌 듯 싶다....

 

 

END.