[Solution] Mainak and the Bleeding Polygon solution codeforces

Mainak and the Bleeding Polygon solution codeforces – Mainak has a convex polygon P with 𝑛n vertices labelled as 𝐴1,𝐴2,,𝐴𝑛A1,A2,…,An in a counter-clockwise fashion.

Table of Contents

[Solution] Mainak and the Bleeding Polygon solution codeforces

The coordinates of the 𝑖i-th point 𝐴𝑖Ai are given by (𝑥𝑖,𝑦𝑖)(xi,yi), where 𝑥𝑖xi and 𝑦𝑖yi are both integers.

Further, it is known that the interior angle at 𝐴𝑖Ai is either a right angle or a proper obtuse angle. Formally it is known that:

  • 90𝐴𝑖1𝐴𝑖𝐴𝑖+1<18090∘≤∠Ai−1AiAi+1<180∘𝑖{1,2,,𝑛}∀i∈{1,2,…,n} where we conventionally consider 𝐴0=𝐴𝑛A0=An and 𝐴𝑛+1=𝐴1An+1=A1.

Mainak’s friend insisted that all points 𝑄Q such that there exists a chord of the polygon P passing through 𝑄Q with length not exceeding 11, must be coloured redred.

Mainak wants you to find the area of the coloured region formed by the redred points.

Formally, determine the area of the region ={𝑄S={Q∈P | 𝑄 is coloured red}Q is coloured red}.

Recall that a chord of a polygon is a line segment between two points lying on the boundary (i.e. vertices or points on edges) of the polygon.

[Solution] Mainak and the Bleeding Polygon solution codeforces

The first line contains an integer 𝑛n (4𝑛50004≤n≤5000) — the number of vertices of a polygon P.

The 𝑖i-th line of the next 𝑛n lines contain two integers 𝑥𝑖xi and 𝑦𝑖yi (109𝑥𝑖,𝑦𝑖109−109≤xi,yi≤109) — the coordinates of 𝐴𝑖Ai.

Additional constraint on the input: The vertices form a convex polygon and are listed in counter-clockwise order. It is also guaranteed that all interior angles are in the range [90;180)[90∘;180∘).

Output

Print the area of the region coloured in redred.

Your answer is considered correct if its absolute or relative error does not exceed 10410−4.

Formally, let your answer be 𝑎a, and the jury’s answer be 𝑏b. Your answer is accepted if and only if |𝑎𝑏|max(1,|𝑏|)104|a−b|max(1,|b|)≤10−4.

[Solution] Mainak and the Bleeding Polygon solution codeforces

input

Copy
4
4 5
4 1
7 1
7 5
output

Copy
1.17809724510
input

Copy
5
-3 3
3 1
4 2
-1 9
-2 9
output

Copy
1.07823651333

[Solution] Mainak and the Bleeding Polygon solution codeforces

In the first example, the polygon P can be visualised on the Cartesian Plane as:

For Solution

“Click Here”

Leave a Comment