PolygonalRegions
SRM 781 · 2020-03-19 · by sinus_070
Problem Statement
There are N points in the plane. These points are the vertices of a strictly convex N-sided polygon. The points are labeled from 1 to N in clockwise order.
The vertices of the polygon are in a general position. In particular, it is guaranteed that no three diagonals of the polygon intersect at the same point.
We are now going to draw the boundary of the polygon and some diagonals, as follows:
- Each vertex is either good or bad. The probability that vertex i is good is (i / N).
- For each vertex i, we draw a line between vertices i and (i % N) + 1: these are the sides of the polygon.
- For each pair of non-adjacent vertices i and j, we draw the diagonal between i and j if and only if both i and j are good.
Once the drawing is done, the inside of the polygon will be divided into some number of regions. Let X be the expected number of those regions. It can be shown that X is always a rational number. Moreover, if we express X as a reduced fraction P / Q, the denominator Q is not a multiple of 1000000007.
Compute and return the value (P * Q^(-1)) modulo 1000000007.
Notes
- A polygon is strictly convex if the angle at each vertex is strictly smaller than 180 degrees.
- The choice whether a vertex is good or bad is only made once and applies to all diagonals from that vertex. It is not made separately for each diagonal.
- Q^(-1) denotes the multiplicative inverse to Q modulo 1000000007. That is, (Q * (Q^(-1)) modulo 1000000007 = 1.
- It can be shown that the answer does not depend on the coordinates of the vertices of the polygon.
Constraints
- N will be between 3 and 100, inclusive.
3 Returns: 1
There is only one region as no diagonals can be drawn.
4 Returns: 31250002
The expect number of regions is equal to 57/32. P(1 region) = P(no diagonal existing) = 13/32 P(2 regions) = P(exactly 1 of the diagonals existing) = 16/32 P(3 regions) = 0 P(4 regions) = P(both diagonals existing) = (1/4) * (2/4) * (3/4) * (4/4) = 3/32 Expected value = (13*1 + 16*2 + 3*4)/32 = 57/32.
10 Returns: 346100029
20 Returns: 123262880
100 Returns: 166669813
Submissions are judged against all 36 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PolygonalRegions with a public method int expectedRegions(int N) · 36 test cases · 2 s / 256 MB per case