BOJ_17386_선분 교차 1 ( Java )

[Gold III] 선분 교차 1 - 17386

문제 링크

성능 요약

메모리: 14284 KB, 시간: 100 ms

분류

기하학, 선분 교차 판정

제출 일자

2024년 9월 17일 10:58:52

문제 설명

2차원 좌표 평면 위의 두 선분 L₁, L₂가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자.

L₁의 양 끝 점은 (x₁, y₁), (x₂, y₂), L₂의 양 끝 점은 (x₃, y₃), (x₄, y₄)이다.

입력

첫째 줄에 L₁의 양 끝 점 x₁, y₁, x₂, y₂가, 둘째 줄에 L₂의 양 끝 점 x₃, y₃, x₄, y₄가 주어진다. 세 점이 일직선 위에 있는 경우는 없다.

출력

L₁과 L₂가 교차하면 1, 아니면 0을 출력한다.

문제 풀이

CCW알고리즘을 이용해 풀었다. CCW 알고리즘이란 두 벡터의 스칼라 곱을 계산하는방법을 응용한 것인데 두 벡터 u, v 의 스칼라 곱 u x v 는 |u||v|sin(theta_) 이다. 이로 인해 두 벡터의 순서에 따라 부호가 정해지고 이를 사용해 4 점을 ccw해보면 x1, y1, x2, y2, x3, y3 곱하기 x1, y1, x2, y2, x4, y4가 음수이면서 (서로 반대방향) x3, y3, x4, y4, x1, y1 곱하기 x3, y3, x4, y4, x2, y2가 음수면 선분이 겹쳐있는 것이고 이 중 하나라도 0이상이면 두 선분이 겹치지 않는다는 뜻이다. 그림으로 그려보면 알 수 있다. 따라서 둘 다 음수 일 때 선분이 겹친하는 의미의 1을 리턴하면 된다.

코드

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

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
//		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		int x1 = Integer.parseInt(st.nextToken());
		int y1 = Integer.parseInt(st.nextToken());
		int x2 = Integer.parseInt(st.nextToken());
		int y2 = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int x3 = Integer.parseInt(st.nextToken());
		int y3 = Integer.parseInt(st.nextToken());
		int x4 = Integer.parseInt(st.nextToken());
		int y4 = Integer.parseInt(st.nextToken());
		
		int ans = 0;
		
		if(ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) < 0 && ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) < 0) ans = 1; 
	
		System.out.println(ans);
	}
	private static int ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
		return x1*y2+x2*y3+x3*y1 - x2*y1-x3*y2-x1*y3 < 0 ? 1 : -1;
	}
}