[백준(Baekjoon)][자바(java)] 20149 : 선분 교차 3 / 기하

 

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

20149번: 선분 교차 3

 

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

public class Main {

	static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { // CounterClockWise
		long value = (long) (x2 - x1) * (y3 - y1) - (long) (x3 - x1) * (y2 - y1);
		return value < 0 ? -1 : value > 0 ? 1 : 0; // -1 : 시계 방향, 1 : 반시계 방향, 0 : 일직선
	}

	static String isIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
		int d123 = ccw(x1, y1, x2, y2, x3, y3), d124 = ccw(x1, y1, x2, y2, x4, y4),
		    d341 = ccw(x3, y3, x4, y4, x1, y1), d342 = ccw(x3, y3, x4, y4, x2, y2); // direction
		int v12 = d123 * d124, v34 = d341 * d342;
		if (v12 == 0 && v34 == 0) {
			if (d123 == 0 && d124 == 0 && d341 == 0 && d342 == 0) { // 네 점이 일직선
				int pA, pB, pC, pD;
				if (x1 == x2)	{ pA = Math.min(y1, y2); pB = Math.max(y1, y2); }
				else 			{ pA = Math.min(x1, x2); pB = Math.max(x1, x2); }
				if (x3 == x4)	{ pC = Math.min(y3, y4); pD = Math.max(y3, y4); }
				else 			{ pC = Math.min(x3, x4); pD = Math.max(x3, x4); }
				if (pC < pB && pA < pD) 	return "1";
				if (pC == pB || pA == pD)	return "1\n" + getSamePoint(x1, y1, x2, y2, x3, y3, x4, y4);
				return "0";
			}
			return "1\n" + getSamePoint(x1, y1, x2, y2, x3, y3, x4, y4); // 세 점이 일직선인데 그 중 두 점이 겹침
		}
		if (v12 <= 0 && v34 <= 0) // 세 점이 일직선인데 두 점 사이에 있거나 / 두 선분이 서로 교차
			return "1\n" + getMeetPoint(x1, y1, x2, y2, x3, y3, x4, y4);
		return "0";
	}
	
	static String getSamePoint(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
		if ((x1 == x3 && y1 == y3) || (x1 == x4 && y1 == y4)) return x1 + " " + y1;
		if ((x2 == x3 && y2 == y3) || (x2 == x4 && y2 == y4)) return x2 + " " + y2;
		return "";
	}
	
	static String getMeetPoint(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
		int a, b, c, d, e, f; double ad_bc, r;
		a = x2 - x1; b = y2 - y1; c = x4 - x3; d = y4 - y3;
		e = x3 - x1; f = y3 - y1; ad_bc = ((long) a * d) - ((long) b * c);
		r = ((long) d * e - (long) c * f) / ad_bc;
		return (a * r + x1) + " " + (b * r + y1);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
		StringTokenizer st;
		int p[][] = new int[4][2], i, j, k, s, e; // p : point, s : start, e : end
		for (k = 0; k < 2; ++k) {
			st = new StringTokenizer(br.readLine());
			s = k * 2; e = s + 2;
			for (i = s; i < e; ++i)
				for (j = 0; j < 2; ++j)
					p[i][j] = Integer.parseInt(st.nextToken());
		}
		br.close();
		System.out.println(isIntersect(p[0][0], p[0][1], p[1][0], p[1][1], p[2][0], p[2][1], p[3][0], p[3][1]));
	}
}

 

p1, p2, p3, p4  4개의 점이 주어지고,
p1, p2 를 이은 선분과
p3, p4 를 이은 선분이
교차하는지 구하는 문제

CCW( CounterClockWise ) 알고리즘을 이용하여
세 점( 네 경우 - 1,2,3 / 1,2,4 / 3,4,1 / 3,4,2 )을 순서대로 이은 선의 방향을 구한 후
*  d123  =  ccw( p1, p2, p3 )
*  d124  =  ccw( p1, p2, p4 )
*  d341  =  ccw( p3, p4, p1 )
*  d342  =  ccw( p3, p4, p2 )
서로 반대인지 일직선인지 판단
*  v12  =  d123 * d124
*  v34  =  d341 * d342
( v12, v34 각각의 값이 -1( 반대 방향 ) 이거나 0( 일직선 ) 이거나 )

 

• v12 < 0  &&  v34 < 0  :  두 선분이 서로 교차함  ( 한 점에서 만남 )  ①
• (v12 == 0  &&  v34 < 0)  ||  (v12 < 0  &&  v34 == 0)  :  세 점이 일직선 상에 있는데 한 점이 다른 두 점 사이에 있음  ( 한 점에서 만남 )  ②
• v12 == 0  &&  v34 == 0  :  세 점 이상이 일직선 상에 있음
  • d123 == 0  &&  d124 == 0  &&  d341 == 0  &&  d342 == 0  :  네 점이 일직선 상에 있음  ③
    • ( p1 & p2, p3 & p4 를 좌표 위치에 따라 pA & pB, pC & pD 라고 할 때 )
    • pC < pB  &&  pA < pD  :  선분이 일직선으로 서로 겹침  ( 무수히 많은 점 )
    • pC == pB  ||  pA == pD  :  두 점이 같고 일직선으로 이어짐  ( 한 점에서 만남 )
    • (나머지)  :  교차하지 않음  ( 만나지 않음 )
  • (나머지)  :  세 점이 일직선 상에 있는데 그 중 두 점이 같음  ( 한 점에서 만남 )  ④

 

각 경우의 예

 

네 점이 일직선인 경우