Under construction

Still being built. Things may change

Polygon Discovery

Time limit4sMemory limit2048 MB

Summary
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 PP located on a two-dimensional coordinate plane. The exact coordinates of the polygon PP are unknown, but you can use a special equipment that allows you to query the number of intersections between a given query line and PP.

The polygon PP is known to be a convex polygon, meaning every line segment between two points inside the polygon is fully contained within its interior. Additionally, PP is non-degenerate, ensuring that its area is strictly greater than zero. The polygon also contains the origin (0,0)(0, 0) strictly within its interior. All vertices of PP have integer coordinates, with each coordinate lying within the range [−1 024,1 023][-1\,024, 1\,023] inclusive.

Write a program to compute the area of the polygon PP by invoking a series of queries.

Examples1

  1. Example 1

    Input
    
    2
    
    0
    
    1
    
    infinity
    
    correct
    
    Expected output
    ? 0 0 1 1
    
    ? -3 -1 0 2
    
    ? 0 -4 4 0
    
    ? 4 3 7 5
    
    ! 5.5