문제
2차원 좌표 평면 위의 세 점 P1, P2, P3가 주어질 때, 이 세 점을 순서대로 이은 선분의 방향(반시계/시계/일직선)을 판별하라.
입력
세 줄에 걸쳐 각 점의 x, y 좌표가 주어진다 (-10,000 ≤ x, y ≤ 10,000).
출력
반시계 방향이면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 1 5 5 7 3 | -1 |
풀이
벡터의 외적(Cross Product)을 이용하여 세 점의 방향성을 판별한다.
- P1→P2 벡터 (m1, n1)과 P1→P3 벡터 (m2, n2)를 구한다
- 외적값 = m1 * n2 - n1 * m2를 계산한다
- 외적값이
> 0이면 반시계(1),< 0이면 시계(-1),= 0이면 일직선(0)
핵심 아이디어: 두 벡터의 외적 부호가 곧 세 점의 회전 방향을 나타낸다. 이는 신발끈 공식(Shoelace formula)의 부호와 동치이다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day161BOJ11758신발끈 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int y1 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int z1 = Integer.parseInt(st.nextToken());
int z2 = Integer.parseInt(st.nextToken());
int m1 = y1 - x1;
int n1 = y2 - x2;
int m2 = z1 - x1;
int n2 = z2 - x2;
int temp = m1 * n2 - n1 * m2;
if (temp > 0)
System.out.println(1);
else if (temp == 0)
System.out.println(0);
else
System.out.println(-1);
br.close();
}
}복잡도
- 시간: O(1)
- 공간: O(1)