ConvexCut
Time limit2sMemory limit512 MB
Given a convex polygon, find a point through which every line cuts the polygon into two equal-area halves, or report that none exists.
- Level
Medium7 of 10
- Topics
- Geometry, Binary search, Implementation, Math
- Solved
- No attempts yet
Problem
A convex polygon with N vertices is given. The coordinates of the vertices are given counterclockwise as (X1, Y1), (X2, Y2), ..., (XN, YN). Find the coordinates of a point P such that cutting the convex polygon by any line through P yields two convex polygons of equal area.
Input
The input is given in the following format.
N
X1 Y1
X2 Y2
......
XN YN
Output
If a point satisfying the condition in the statement exists, output its coordinates in the format
X Y
If no such point exists, output "NA" on a single line.
Constraints
-
All input values are integers.
-
3 ≤ N ≤ 50
-
0 ≤ |Xi|, |Yi| ≤ 1000000
-
The polygon given in the input is a simple convex polygon.
-
Letting the output coordinates be (X, Y) and the exact answer be (cX, cY), the output must satisfy max(|X-cX|, |Y-cY|) ≤ 0.0001.