시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 198 | 46 | 39 | 25.658% |
Bob and Alice are roommates at the International College of Polygonal Chambers (ICPC). To avoid conflict, they've agreed to divide their dorm room in half---as closely as possible. However, the room is shaped so irregularly that they need your help!
Each dorm room is a convex polygon, with a single entrance. You need to figure out how to divide this room in half (by area) using a single straight line starting at the door, and terminating on a wall or corner of the room.
The first line of input contains a single integer $n$ ($3 \leq n \leq 2 \cdot 10^5$), which is the number of vertices describing the convex polygon.
Each of the next $n$ lines contains two space-separated integers $x$ and $y$ ($-10^7 \le x,y \le 10^7$). These are the coordinates of the vertices of the convex polygon, in counterclockwise order. All points will be distinct.
The door is considered to be a single point located at the first vertex given in the input.
Output two space-separated real numbers, which are the $x$ and $y$ coordinates of the other endpoint of the dividing line, such that the area of the room is divided in half. Each coordinate value must be accurate to within an absolute or relative error of $10^{-6}$. Output $x$ first, then $y$.
Note that Sample 1 corresponds to the example in the problem description.
5 7 1 8 3 5 5 2 3 3 1
3.5 4
3 2 2 10 3 6 8
8 5.5
ICPC > Regionals > North America > Pacific Northwest Regional > 2021 ICPC Pacific Northwest Region > Division 1 L번
ICPC > Regionals > North America > Pacific Northwest Regional > 2021 ICPC Pacific Northwest Region > Division 2 Y번
ICPC > Regionals > North America > South Central USA Regional > 2021 South Central USA Regional Contest > Division 1 D번
ICPC > Regionals > North America > South Central USA Regional > 2021 South Central USA Regional Contest > Division 2 D번
ICPC > Regionals > North America > Mid-Central Regional > Mid-Central USA Programming Contest 2021 D번
ICPC > Regionals > North America > Northeast North America Regional > 2021 Northeast North America Regional Contest D번
ICPC > Regionals > North America > Southeast USA Regional > 2021 Southeast USA Regional Programming Contest > Division 1 D번
ICPC > Regionals > North America > Southeast USA Regional > 2021 Southeast USA Regional Programming Contest > Division 2 D번