Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

32. 기하

조금 더 어려운 기하 문제를 풀어 봅시다.

Java / Python

3. 선분 교차 1

17386번

두 선분의 교차를 판별하는 문제

이번 문제는 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구하는 문제이다. L1과 L2가 교차하면 1, 아니면 0을 출력한다.

CCW를 이용하는 문제이다.

• Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		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());

		char result = '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) result = '1';

		bw.write(result + "\n");

		bw.flush();
		bw.close();
		br.close();
	}

	public static int ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
		// CCW 공식 (x1y2+x2y3+x3y1)−(y1x2+y2x3+y3x1)
		return x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1 < 0 ? 1 : -1;
	}
}

• Python

import sys
input = sys.stdin.readline

x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())

A, B, C, D = [x1,y1], [x2,y2], [x3,y3], [x4,y4]

def ccw(p1, p2, p3):
    return (p1[0]*p2[1] + p2[0]*p3[1] + p3[0]*p1[1]) - (p2[0]*p1[1] + p3[0]*p2[1] + p1[0]*p3[1])

if ccw(A,B,C)*ccw(A,B,D) < 0 and ccw(C,D,A)*ccw(C,D,B) < 0:
    print(1)
else:
    print(0)