[백준 17387] 선분 교차 2

https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

 

 

진짜진짜 금방 풀 줄 알았는데..

"세 점은 평행하지 않는다" 란 조건 하나가 빠지니까 신경써야 할 경우의 수들이 우수수.. 나오더라?

 

여튼 1 버전에 비교해서 추가된 상황을 생각하여 보면

 

1. 한 선분이 다른 선분을 포함함

 

ex) 

1 1 5 5
5 5 1 1

1 1 5 5
3 3 4 4

 

2. 두 점이 겹침

 

ex)

1 1 5 5
5 5 9 9

1 1 5 5
5 5 1 5

 

3. 한 점이 다른 선분 안에 있음 

 

ex)

1 1 5 5
3 3 1 3

 

 

위처럼 추가된 경우로 인해, 

ccw을 이용하여 선분의 교차 여부를 판단하는 방법이 복잡해졌다.

 점의 일치 여부를 판단하고 선분의 평행 여부를 판단하고 또 그 평행한 선분이 다른 선분에 포함되는 지를 판단하고..

 

 

따라서 다음과 같이 코드를 작성했다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        double segment[] = new double[4];
        double segment2[] = new double[4];
        String line = br.readLine();
        segment = Arrays.stream(line.split(" ")).mapToDouble(Double::parseDouble).toArray();
        double dotA[] = Arrays.copyOfRange(segment, 0, 2);
        double dotB[] = Arrays.copyOfRange(segment, 2, segment.length);

        line = br.readLine();
        segment = Arrays.stream(line.split(" ")).mapToDouble(Double::parseDouble).toArray();
        double dotC[] = Arrays.copyOfRange(segment, 0, 2);
        double dotD[] = Arrays.copyOfRange(segment, 2, segment.length);

        if (isCross(dotA, dotB, dotC, dotD))  {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    private static boolean isCross(double a[], double b[], double c[], double d[]) {
        //겹치는 점
        if (Arrays.equals(a, c) || Arrays.equals(a, d) || Arrays.equals(b, c) || Arrays.equals(b, d)) {
            return true;
        }

        boolean flatFlag = false;
        int sum1;
        int sumA, sumB;
        sumA = ccw(a, b, c);
        sumB = ccw(a, b, d);

        sum1 = sumA * sumB;
        if (sumA == 0 && sumB == 0) flatFlag = true;

        int sum2;
        sumA = ccw(c, d, a);
        sumB = ccw(c, d, b);

        sum2 = sumA * sumB;

        //평행 선분 판별
        if (sumA == 0 && sumB == 0 && flatFlag == true) flatFlag = true;
        else flatFlag = false;

        if (sum1 == 1 || sum2 == 1 ) {
            return false;
        }else if(flatFlag ==true){ //평행
            if ((between(a, b, c) || between(a, b, d)) || (between(c, d, a) || between(c, d, b))) { //포함
                return true;
            } else {
                return false;
            }
        } else {
            return true;
        }
    }

    private static int ccw(double a[], double b[], double c[]) {
        double ans;
        ans = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);

        if(ans==0)  return 0;
        else if(ans>0)  return 1;
        else    return -1;

    }

    //ab에 대한 c의 포함 여부
    private static boolean between(double a[], double b[], double c[]) {
        double lL[] = (a[0] < b[0]) ? a : b;
        double lR[] = (a[0] > b[0]) ? a : b;

        if(c[0]>=lL[0] && c[0]<lR[0])
            return true;
        else
            return false;
    }
}