문제
'별 모양'을 수학적으로 정의해 보자. 평면 위의 어떤 도형이 별 모양일 필요충분조건은 도형 안에 어떤 점 C가 있어서, 도형 안의 모든 점 P에 대해 선분 CP가 도형에 포함되는지 여부이다. 아래는 별 모양 도형의 예이다.
첫 줄에 위치한 모든 도형은 별 모양이지만, 두 번째 줄에 위치한 도형은 별 모양이 아니다. 주어진 다각형이 별 모양인지 아닌지 구하여라.
입력
입력은 여러 개의 테스트 케이스로 구성된다. 각 테스트 케이스는 다각형을 의미하며 아래 형식으로 주어진다.
n
x1 y1
x2 y2
…
xn yn
첫 행에는 꼭지점의 수 n 이 주어지며 4≤n≤50 이다.
다음 n 행에 걸쳐 x와 y 좌표가 주어진다. 모든 좌표는 정수이며 0≤xi≤10,000, 0≤yi≤10,000 (i=1 … n) 이다.
선분 (xi yi)-(xi+1 yi+1) (i=1, …, n ? 1)과 선분 (xn yn)-(x1 y1)는 반시계방향을 이룬다.
주어진 다각형은 단순 다각형이다.
단순 다각형이라 함은 다각형을 구성하는 선분이 꼭지점을 제외하고 서로 닿거나 교차하지 않는다는 뜻이다.
덧붙여 다각형의 세 선분을 골라 직선으로 이었을 때 세 직선이 한 점에서 만나는 경우는 없다.
출력
각 테스트 케이스에 대해 한 행에 하나씩 차례로 별 모양이면 1, 아니면 0을 출력한다.
예제
6
66 13
96 61
76 98
13 94
4 0
45 68
8
27 21
55 14
93 12
56 95
15 48
38 46
51 65
64 31
0
10
로그인해야 코드를 작성할 수 있어요.