ConvexCut

시간 제한2초메모리 제한512 MB

요약

볼록 다각형이 주어질 때, 그 점을 지나는 임의의 직선이 다각형을 같은 넓이의 두 조각으로 나누는 점을 찾고, 없으면 NA를 출력한다.

난이도: 보통10점 중 7점
유형: 기하, 이분 탐색, 구현, 수학
정답자: 아직 제출이 없습니다

문제

N개의 꼭짓점으로 이루어진 볼록 다각형이 주어진다. 각 꼭짓점의 좌표는 반시계 방향으로 (X1, Y1), (X2, Y2), ..., (XN, YN)으로 주어진다. 점 P를 지나는 어떤 직선으로 볼록 다각형을 잘라도, 자른 뒤 얻어지는 두 볼록 다각형의 넓이가 같아지는 점 P의 좌표를 구하시오.

입력

입력은 다음 형식으로 주어진다.

N
X1 Y1
X2 Y2
......
XN YN

출력

문제의 조건을 만족하는 점이 있으면 그 점의 좌표를

X Y

형식으로 출력한다. 점이 존재하지 않으면 "NA"를 한 줄에 출력한다.

제한

입력은 모두 정수이다.
3 ≤ N ≤ 50
0 ≤ |Xi|, |Yi| ≤ 1000000
입력으로 주어지는 다각형은 단순한 볼록 다각형이다.
출력 좌표를 (X, Y), 정확한 답을 (cX, cY)라 할 때 max(|X-cX|, |Y-cY|) ≤ 0.0001을 만족해야 한다.

예제2

예제 1

입력

예상 출력

50.00000 50.00000

예제 2
입력
```
3
100 100
0 100
0 0
```
예상 출력
```
NA
```