[백준] 11758 - CCW

[백준] 11758 - CCW

[문제링크]

0. 수학, 기하학 문제

1. P1, P2, P3를 이은 선이 시계방향인지 아닌지 알려면 P1-P2, P1-P3선의 기울기를 비교하면 된다

위 그림과 같이, 1-2-3처럼 반시계방향일때는 1-2보다 1-3의 기울기가 크고,

반대로 1-2-3'처럼 시계방향일때는 1-2보다 1-3이 작다

2. 두 점으로부터 기울기는 간단하게 (y2-y1)/ (x2-x1) 로 얻을 수 있다

하지만 나누기 연산으로 정확도 문제가 발생하게 된다

3. 필요한것은 두 기울기의 비교이지 정확한 값이 아니므로, 양 측에 (x2-x1) * (x3-x1)을 곱해줘서 정수로 비교한다

(y2-y1) / (x2-x1) ○ (y3-y1) / (x3-x1) 에서

(y2-y1) * (x3-x1) ○ (y3-y1) * (x2-x1) 으로

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int x1 = pint(st.nextToken()); int y1 = pint(st.nextToken()); st = new StringTokenizer(br.readLine()); int x2 = pint(st.nextToken()); int y2 = pint(st.nextToken()); st = new StringTokenizer(br.readLine()); int x3 = pint(st.nextToken()); int y3 = pint(st.nextToken()); int line1 = (y3-y1)*(x2-x1); // 1-3 int line2 = (y2-y1)*(x3-x1); // 1-2 if(line1 == line2)System.out.println(0); else if(line1 > line2)System.out.println(1); else System.out.println(-1); } static int pint(String s) { return Integer.parseInt(s); } }

결과 화면

from http://nato-blog.tistory.com/153 by ccl(S) rewrite - 2021-11-16 03:01:51