Polygon Discovery
Time limit4sMemory limit2048 MB
Find the area of a hidden convex lattice polygon containing the origin, using queries that return how many times a given line crosses the polygon.
- Level
Medium6 of 10
- Topics
- Geometry, Math, Binary search
- Solved
- No attempts yet
Problem
You are a member of the research team CPCI (Convex Polygon Computational Investigation), tasked with uncovering the properties of an unknown simple polygon located on a two-dimensional coordinate plane. The exact coordinates of the polygon are unknown, but you can use a special equipment that allows you to query the number of intersections between a given query line and .
The polygon is known to be a convex polygon, meaning every line segment between two points inside the polygon is fully contained within its interior. Additionally, is non-degenerate, ensuring that its area is strictly greater than zero. The polygon also contains the origin strictly within its interior. All vertices of have integer coordinates, with each coordinate lying within the range inclusive.
Write a program to compute the area of the polygon by invoking a series of queries.