Detailed mathematical approach

Problem Summary

The problem generates a deterministic set of 500 integer points and asks for the largest-area convex polygon whose interior contains no other generated point. In computational geometry this is a largest convex hole.

The point set is not arbitrary: it comes from the recurrence

$s_0=290797,\qquad s_n=s_{n-1}^2\bmod 50515093,$

$t_n=(s_n\bmod 2000)-1000,$

and the points are

$P_i=(t_{2i-1},t_{2i})\qquad(1\le i\le 500).$

The code does not enumerate polygons directly. Instead, it reduces the problem to fast emptiness tests for triangles and a dynamic program over angularly ordered vertices.

Mathematical Approach

Point Generation

The recurrence above produces the first three points

$P_1=(527,144),\qquad P_2=(-488,732),\qquad P_3=(-454,-947).$

The oriented doubled area of this triangle is

$\operatorname{cross}(P_1,P_2,P_3)=1684193,$

so its ordinary area is \(842096.5\). This already explains why the implementation stores doubled areas as integers: all coordinates are integral, so every polygon area is an integer multiple of \(1/2\).

Cross Product and Doubled Area

For three points \(A,B,C\), define

$\operatorname{cross}(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$

This quantity is positive for a left turn, negative for a right turn, and zero for collinearity. Geometrically,

$|\operatorname{cross}(A,B,C)|=2\,[ABC],$

where \([ABC]\) denotes the Euclidean area of triangle \(ABC\). Using doubled area avoids all floating-point roundoff during the DP.

Left-of-Edge Sets and Empty Triangles

For every directed edge \((a,b)\), the code precomputes the set

$L(a,b)=\{p:\operatorname{cross}(a,b,p)\gt 0\},$

that is, all generated points lying strictly to the left of the oriented line from \(a\) to \(b\).

If triangle \((a,b,c)\) is oriented counterclockwise, then a point \(p\) lies strictly inside it exactly when

$p\in L(a,b)\cap L(b,c)\cap L(c,a).$

Therefore the triangle is strictly empty if and only if

$L(a,b)\cap L(b,c)\cap L(c,a)=\varnothing.$

This criterion is ideal for bitsets: emptiness reduces to a few word-wise AND operations.

The word “strictly” matters. The problem forbids points in the interior of the polygon, but points on the boundary are allowed. That is why the test uses \(\gt 0\) instead of \(\ge 0\).

Why Anchors Are Enough

Every convex polygon has a unique lowest vertex; if several vertices have the same \(y\)-coordinate, the leftmost among them is unique. Call this vertex the anchor \(A\).

Then every other vertex \(v\) of the polygon must satisfy

$v_y>A_y\quad\text{or}\quad(v_y=A_y\text{ and }v_x>A_x).$

So once \(A\) is fixed, every admissible polygon using \(A\) lies entirely in the upper half-plane relative to the horizontal through \(A\). The code uses exactly this fact to build the candidate list for each anchor.

It then sorts those candidates by polar angle around \(A\). For a convex polygon containing \(A\) as lowest-leftmost vertex, this angular order is precisely the boundary order of the remaining vertices.

Dynamic Programming on Convex Chains

Fix an anchor \(A\), and let the angle-sorted candidates be

$v_0,v_1,\dots,v_{m-1}.$

The DP state \(dp[j,k]\) stores the largest doubled area of an empty convex chain

$A\to \cdots \to v_j \to v_k$

whose final edge is \((v_j,v_k)\). The base case is the triangle \(A,v_j,v_k\), whose doubled area contribution is

$\Delta(A,v_j,v_k)=\operatorname{cross}(A,v_j,v_k).$

If \(\Delta\le 0\), the triple is not counterclockwise and cannot be part of the chain.

The transition is

$dp[j,k]=\max\Big(\Delta(A,v_j,v_k),\max_h\{dp[h,j]+\Delta(A,v_j,v_k)\}\Big),$

subject to three constraints:

1. The triangle \((A,v_j,v_k)\) must be strictly empty.

2. The turn at \(v_j\) must stay convex:

$\operatorname{cross}(v_h,v_j,v_k)\gt 0.$

3. The segment \((A,v_j)\) may not contain another generated point in its open interior when it is used as an internal diagonal.

Why the Collinearity Check Matters

The code precomputes a Boolean flag has_inner_collinear[a][b] that records whether some generated point lies on the open segment from \(a\) to \(b\).

This is not needed for boundary edges of the final polygon, because boundary points are allowed. But when the DP extends a chain through \(v_j\), the segment \((A,v_j)\) becomes an internal diagonal of the anchor fan triangulation. If another point lay on that open segment, it would lie in the polygon interior, which is forbidden. Hence such transitions are blocked.

Why the DP Computes the Correct Maximum

Take any empty convex polygon and choose its lowest-leftmost vertex as anchor \(A\). Its remaining vertices appear in increasing angular order around \(A\), and the polygon can be triangulated into the fan

$ (A,v_{i_1},v_{i_2}),\ (A,v_{i_2},v_{i_3}),\ \dots .$

Because the polygon interior is empty, each of these triangles is strictly empty. Because the polygon is convex, consecutive triples make only left turns. Therefore every valid polygon corresponds to a valid DP chain, and the chain area is exactly the sum of its triangle contributions.

Conversely, any DP chain satisfying the emptiness, left-turn, and diagonal constraints reconstructs an empty convex polygon with anchor \(A\). So the DP searches exactly the feasible family and maximizes its area.

Validation Checkpoint

The C++ code includes a checkpoint for the first 20 generated points. It verifies that the maximum doubled area is

$2099389,$

which corresponds to the area

$1049694.5.$

This is useful both as a correctness test and as a reminder that half-integer areas naturally arise.

How the Code Works

The implementation has four main stages. First, it generates the 500 points from the pseudo-random recurrence. Second, it precomputes for every directed pair \((a,b)\) both the left-of-edge bitset \(L(a,b)\) and the flag telling whether the open segment \(ab\) contains a generated point. Third, for each anchor \(A\), it filters the candidate vertices above/right of \(A\), sorts them by angle, and runs the chain DP described above. Finally, it takes the best doubled area among all anchors and prints it as either .0 or .5.

Complexity Analysis

Let \(n=500\). The bitset table contains one bitset for each ordered pair of vertices, so its size is

$O\!\left(n^2\cdot \left\lceil \frac{n}{64}\right\rceil\right)=O\!\left(\frac{n^3}{64}\right)$

machine words, plus an \(O(n^2)\) table for the collinearity flags.

The geometric precomputation scans every triple \((a,b,p)\), so its arithmetic cost is \(O(n^3)\), but the later emptiness tests become very fast because they are bit-parallel.

For a fixed anchor with \(m\) visible candidates, the DP is quadratic in the state space and cubic in the worst case when all transitions are possible:

$O(m^3).$

In practice, the emptiness tests, orientation pruning, and incoming-edge filtering discard many transitions. The outer loop over anchors is parallelized across threads.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=252
2. Cross products and orientation tests: cp-algorithms — Basic Geometry
3. Shoelace formula / polygon area: Wikipedia — Shoelace formula
4. Convex hull and related structures: Wikipedia — Convex hull
5. Bit array / bitset background: Wikipedia — Bit array