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.
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\).
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.
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\).
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.
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.
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.
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.
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.
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.
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.
Das Problem erzeugt deterministisch 500 Gitterpunkte und sucht unter ihnen das konvexe Polygon maximaler Fläche, dessen Inneres keinen weiteren erzeugten Punkt enthält. In der diskreten Geometrie nennt man dies ein größtes convex hole.
Die Punkte stammen aus der Rekursion
$$s_0=290797,\qquad s_n=s_{n-1}^2\bmod 50515093,$$
$$t_n=(s_n\bmod 2000)-1000,$$
und werden als
$$P_i=(t_{2i-1},t_{2i})\qquad(1\le i\le 500)$$
gebildet. Der Code durchsucht nicht direkt alle Polygone, sondern reduziert das Problem auf schnelle Leerheitsprüfungen für Dreiecke und ein dynamisches Programm über winkelseitig sortierte Punkte.
Aus der Rekursion entstehen als erste drei Punkte
$$P_1=(527,144),\qquad P_2=(-488,732),\qquad P_3=(-454,-947).$$
Die orientierte doppelte Fläche dieses Dreiecks ist
$$\operatorname{cross}(P_1,P_2,P_3)=1684193,$$
also beträgt die gewöhnliche Fläche \(842096.5\). Genau deshalb arbeitet die Implementierung intern mit doppelten Flächen: Bei ganzzahligen Koordinaten sind alle Polygonflächen ganzzahlige Vielfache von \(1/2\).
Für drei Punkte \(A,B,C\) definiert man
$$\operatorname{cross}(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
Dieser Ausdruck ist positiv bei einer Linksdrehung, negativ bei einer Rechtsdrehung und null bei Kollinearität. Geometrisch gilt
$$|\operatorname{cross}(A,B,C)|=2\,[ABC],$$
wobei \([ABC]\) die gewöhnliche Dreiecksfläche bezeichnet. Durch die Speicherung der doppelten Fläche vermeidet der Code Gleitkommaarithmetik vollständig.
Für jede gerichtete Kante \((a,b)\) wird die Menge
$$L(a,b)=\{p:\operatorname{cross}(a,b,p)\gt 0\}$$
vorkomputiert, also alle erzeugten Punkte, die strikt links der gerichteten Geraden von \(a\) nach \(b\) liegen.
Ist ein Dreieck \((a,b,c)\) gegen den Uhrzeigersinn orientiert, dann liegt ein Punkt \(p\) genau dann strikt im Inneren, wenn
$$p\in L(a,b)\cap L(b,c)\cap L(c,a).$$
Somit ist das Dreieck genau dann streng leer, wenn
$$L(a,b)\cap L(b,c)\cap L(c,a)=\varnothing.$$
Diese Bedingung ist ideal für Bitsets: Leerheit wird zu einigen wortweisen AND-Operationen.
Das Wort „streng“ ist wichtig. Das Problem verbietet Punkte im Inneren des Polygons, erlaubt aber Punkte auf dem Rand. Deshalb wird \(\gt 0\) und nicht \(\ge 0\) verwendet.
Jedes konvexe Polygon besitzt einen eindeutig tiefsten Eckpunkt; bei gleicher \(y\)-Koordinate ist zusätzlich der linkeste eindeutig. Diesen Punkt nennen wir den Anker \(A\).
Dann erfüllt jeder andere Polygonpunkt \(v\)
$$v_y>A_y\quad\text{oder}\quad(v_y=A_y\text{ und }v_x>A_x).$$
Ist also \(A\) fest, dann liegen alle übrigen Ecken in der oberen Halbebene relativ zur Horizontalen durch \(A\). Genau diese Tatsache nutzt der Code bei der Kandidatenauswahl pro Anker.
Anschließend werden diese Kandidaten nach Polarwinkel um \(A\) sortiert. Für ein konvexes Polygon mit niedrigstem-linkstem Eckpunkt \(A\) ist diese Winkelreihenfolge gerade die Randreihenfolge der restlichen Ecken.
Sei \(A\) fest und seien die nach Winkel sortierten Kandidaten
$$v_0,v_1,\dots,v_{m-1}.$$
Der Zustand \(dp[j,k]\) speichert die größte doppelte Fläche einer leeren konvexen Kette
$$A\to \cdots \to v_j \to v_k,$$
deren letzte Kante also \((v_j,v_k)\) ist. Der Grundbaustein ist das Dreieck \(A,v_j,v_k\) mit Flächenbeitrag
$$\Delta(A,v_j,v_k)=\operatorname{cross}(A,v_j,v_k).$$
Falls \(\Delta\le 0\), ist das Tripel nicht gegen den Uhrzeigersinn orientiert und damit unzulässig.
Die Übergangsformel lautet
$$dp[j,k]=\max\Big(\Delta(A,v_j,v_k),\max_h\{dp[h,j]+\Delta(A,v_j,v_k)\}\Big),$$
unter drei Nebenbedingungen:
1. Das Dreieck \((A,v_j,v_k)\) muss streng leer sein.
2. Die Drehung in \(v_j\) muss konvex bleiben:
$$\operatorname{cross}(v_h,v_j,v_k)\gt 0.$$
3. Das Segment \((A,v_j)\) darf in seinem offenen Inneren keinen weiteren erzeugten Punkt enthalten, sobald es als innere Diagonale verwendet wird.
Der Code berechnet zusätzlich ein Bool-Flag has_inner_collinear[a][b], das festhält, ob auf dem offenen Segment von \(a\) nach \(b\) ein erzeugter Punkt liegt.
Für echte Randkanten des endgültigen Polygons ist das unproblematisch, denn Randpunkte sind erlaubt. Wenn die DP aber über \(v_j\) erweitert wird, wird \((A,v_j)\) zu einer inneren Diagonale der Fächertriangulierung. Lägen dort weitere Punkte, so befänden sie sich im Inneren des Polygons, was verboten ist. Solche Übergänge werden deshalb ausgeschlossen.
Betrachte ein beliebiges leeres konvexes Polygon und wähle seinen niedrigsten-linksten Eckpunkt als Anker \(A\). Die übrigen Ecken erscheinen dann in wachsender Winkelreihenfolge um \(A\), und das Polygon zerfällt in den Fächer
$$ (A,v_{i_1},v_{i_2}),\ (A,v_{i_2},v_{i_3}),\ \dots .$$
Da das Polygoninnere leer ist, sind all diese Dreiecke streng leer. Da das Polygon konvex ist, erzeugen aufeinanderfolgende Tripel nur Linksdrehungen. Also entspricht jedes gültige Polygon einer zulässigen DP-Kette, und ihre Fläche ist genau die Summe der Dreiecksbeiträge.
Umgekehrt rekonstruiert jede DP-Kette, die Leerheit, Linksdrehung und Diagonalenbedingung erfüllt, ein leeres konvexes Polygon mit Anker \(A\). Die DP durchsucht also genau die zulässige Familie und maximiert ihre Fläche.
Der C++-Code enthält einen Checkpoint für die ersten 20 erzeugten Punkte. Dort wird überprüft, dass die maximale doppelte Fläche
$$2099389$$
beträgt, also die gewöhnliche Fläche
$$1049694.5.$$
Das dient sowohl als Korrektheitstest als auch als Erinnerung daran, dass Halbzahlen hier ganz natürlich auftreten.
Die Implementierung besitzt vier Hauptphasen. Zuerst werden die 500 Punkte aus der pseudozufälligen Rekursion erzeugt. Zweitens werden für jedes gerichtete Paar \((a,b)\) sowohl das Links-vom-Rand-Bitset \(L(a,b)\) als auch das Flag für innere Kollinearität auf dem offenen Segment \(ab\) vorkomputiert. Drittens wird für jeden Anker \(A\) die Kandidatenmenge oberhalb/rechts von \(A\) gebildet, nach Winkel sortiert und das oben beschriebene Ketten-DP ausgeführt. Viertens wird das beste Ergebnis über alle Anker genommen und als Zahl mit Endung .0 oder .5 ausgegeben.
Sei \(n=500\). Die Bitset-Tabelle enthält für jedes geordnete Paar von Punkten ein Bitset und besitzt daher Größe
$$O\!\left(n^2\cdot \left\lceil \frac{n}{64}\right\rceil\right)=O\!\left(\frac{n^3}{64}\right)$$
Maschinenwörter, zusätzlich zu einer \(O(n^2)\)-Tabelle für die Kollinearitätsflags.
Die geometrische Vorverarbeitung betrachtet jedes Tripel \((a,b,p)\) und kostet arithmetisch \(O(n^3)\), macht die späteren Leerheitsprüfungen aber bit-parallel sehr schnell.
Für einen festen Anker mit \(m\) sichtbaren Kandidaten ist der Zustandsraum quadratisch und die Worst-Case-Laufzeit kubisch:
$$O(m^3).$$
In der Praxis schneiden Leerheitstests, Orientierungsbedingungen und die eingehenden Kantenlisten viele Übergänge weg. Die äußere Schleife über die Anker wird parallel über Threads verteilt.
Problem, deterministik olarak üretilen 500 tamsayı noktasından içinde başka üretilmiş nokta bulunmayan en büyük alanlı dışbükey çokgeni arar. Hesaplamalı geometride buna en büyük convex hole denir.
Noktalar şu üreteçten gelir:
$$s_0=290797,\qquad s_n=s_{n-1}^2\bmod 50515093,$$
$$t_n=(s_n\bmod 2000)-1000,$$
ve noktalar
$$P_i=(t_{2i-1},t_{2i})\qquad(1\le i\le 500)$$
olarak tanımlanır. Kod, çokgenleri doğrudan denemez; bunun yerine problemi boş üçgen testlerine ve açısal olarak sıralanmış köşeler üzerinde bir dinamik programa indirger.
Bu üreteçten çıkan ilk üç nokta şunlardır:
$$P_1=(527,144),\qquad P_2=(-488,732),\qquad P_3=(-454,-947).$$
Bu üçgenin yönlü iki kat alanı
$$\operatorname{cross}(P_1,P_2,P_3)=1684193$$
olur; dolayısıyla gerçek alan \(842096.5\)'tir. Kodun alanları kayan nokta yerine iki kat alan olarak tamsayı saklamasının sebebi budur: tamsayı koordinatlı çokgenlerin alanı her zaman \(1/2\)'nin tam katıdır.
Üç nokta \(A,B,C\) için
$$\operatorname{cross}(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x)$$
tanımlanır. Bu ifade sola dönüşte pozitif, sağa dönüşte negatif, kollineerlikte sıfırdır. Geometrik olarak
$$|\operatorname{cross}(A,B,C)|=2\,[ABC]$$
olur; burada \([ABC]\) üçgen alanıdır. Kodun tüm alan hesabını iki kat alan üzerinden yapması, kayan nokta hatalarını tamamen ortadan kaldırır.
Her yönlü kenar \((a,b)\) için şu küme önceden hesaplanır:
$$L(a,b)=\{p:\operatorname{cross}(a,b,p)\gt 0\}.$$
Yani bu küme, \(a\)'dan \(b\)'ye giden doğru parçasının kesin olarak solunda kalan üretilmiş noktaları içerir.
Eğer \((a,b,c)\) üçgeni saat yönünün tersine yönlenmişse, bir \(p\) noktasının üçgenin kesin iç bölgesinde olması tam olarak
$$p\in L(a,b)\cap L(b,c)\cap L(c,a)$$
koşuluna denktir. Dolayısıyla üçgenin strictly empty olması, yani içinde nokta bulunmaması, şu koşulla eşdeğerdir:
$$L(a,b)\cap L(b,c)\cap L(c,a)=\varnothing.$$
Bu kriter bitset için çok uygundur: boşluk testi birkaç kelime-seviyesinde AND işlemi haline gelir.
Burada “strictly” sözcüğü önemlidir. Problem, çokgenin içinde nokta bulunmamasını ister; sınırdaki noktalar yasak değildir. Bu yüzden testte \(\ge 0\) değil, \(\gt 0\) kullanılır.
Her dışbükey çokgenin tek bir “en aşağı” köşesi vardır; aynı \(y\) değerinde birden fazla köşe varsa, soldaki olan tektir. Bu köşeye anchor \(A\) diyelim.
O zaman çokgenin diğer bütün köşeleri
$$v_y>A_y\quad\text{veya}\quad(v_y=A_y\text{ ve }v_x>A_x)$$
koşulunu sağlar. Dolayısıyla \(A\) sabitlendiğinde, diğer köşeler \(A\)'nın yatay doğrultusunun üst yarı düzleminde kalır. Kod, her anchor için aday kümesini tam olarak bu gözleme göre kurar.
Ardından adayları \(A\) etrafındaki polar açılarına göre sıralar. En aşağı-sol köşe \(A\) olan dışbükey bir çokgende, bu açı sırası aynı zamanda çokgen sınırının sırasıdır.
Bir anchor \(A\) sabitlensin ve açıya göre sıralı adaylar
$$v_0,v_1,\dots,v_{m-1}$$
olsun. \(dp[j,k]\) durumu, son kenarı \((v_j,v_k)\) olan boş bir dışbükey zincirin
$$A\to \cdots \to v_j \to v_k$$
en büyük iki kat alanını tutar. Taban yapı taşı \(A,v_j,v_k\) üçgenidir ve katkısı
$$\Delta(A,v_j,v_k)=\operatorname{cross}(A,v_j,v_k)$$
şeklindedir. Eğer \(\Delta\le 0\) ise yön saat yönünün tersine değildir ve bu üçlü kullanılamaz.
Geçiş bağıntısı:
$$dp[j,k]=\max\Big(\Delta(A,v_j,v_k),\max_h\{dp[h,j]+\Delta(A,v_j,v_k)\}\Big)$$
biçimindedir; ancak üç ek koşul gerekir:
1. \((A,v_j,v_k)\) üçgeni strict olarak boş olmalıdır.
2. \(v_j\) noktasındaki dönüş dışbükey kalmalıdır:
$$\operatorname{cross}(v_h,v_j,v_k)\gt 0.$$
3. \((A,v_j)\) doğru parçası, iç diyagonal olarak kullanıldığında açık iç kısmında başka üretilmiş nokta barındırmamalıdır.
Kod ayrıca has_inner_collinear[a][b] adlı bir Boolean tablo hesaplar. Bu tablo, \(a\) ile \(b\) arasındaki açık doğru parçası üzerinde başka üretilmiş nokta olup olmadığını söyler.
Bu bilgi son çokgenin gerçek sınır kenarları için şart değildir; çünkü sınırdaki noktalar serbesttir. Ancak DP, \(v_j\) üzerinden bir zinciri uzattığında \((A,v_j)\) bir iç diyagonal haline gelir. Eğer bu açık parça üzerinde başka nokta olsaydı, o nokta çokgenin içine düşerdi. Bu yüzden kod böyle geçişleri yasaklar.
Herhangi bir boş dışbükey çokgen alın ve en aşağı-sol köşesini anchor \(A\) seçin. Geri kalan köşeler \(A\) etrafında artan açı sırasındadır ve çokgen şu fan üçgenlerine ayrılabilir:
$$ (A,v_{i_1},v_{i_2}),\ (A,v_{i_2},v_{i_3}),\ \dots .$$
Çokgenin içi boş olduğu için bu üçgenlerin her biri strict olarak boştur. Çokgen dışbükey olduğu için ardışık üçlülerde yalnızca sola dönüş oluşur. Dolayısıyla her geçerli çokgen, geçerli bir DP zincirine karşılık gelir ve alanı, bu üçgen katkılarının toplamıdır.
Tersine, boşluk, sola dönüş ve iç diyagonal koşullarını sağlayan her DP zinciri de anchor'ı \(A\) olan boş bir dışbükey çokgen oluşturur. Yani DP tam olarak doğru aday ailesini tarar ve bunlar arasında alanı maksimize eder.
C++ kodu, ilk 20 üretilmiş nokta için bir checkpoint içerir. Burada en büyük iki kat alanın
$$2099389$$
olduğu doğrulanır; bu da
$$1049694.5$$
alanına karşılık gelir. Bu hem doğruluk testi olarak hem de alanların doğal olarak yarım sayılı olabileceğini göstermek için yararlıdır.
Uygulama dört ana fazdan oluşur. Önce pseudo-random üreteçten 500 nokta üretilir. Sonra her yönlü \((a,b)\) çifti için hem \(L(a,b)\) bitset'i hem de açık \(ab\) parçasında nokta olup olmadığını belirten işaret önceden hesaplanır. Üçüncü aşamada her anchor \(A\) için \(A\)'nın üstünde/sağında kalan adaylar seçilir, açıya göre sıralanır ve yukarıdaki zincir DP'si çalıştırılır. Son aşamada tüm anchor'lar arasındaki en iyi iki kat alan alınır ve çıktı .0 ya da .5 biçiminde yazdırılır.
\(n=500\) olsun. Bitset tablosu her sıralı nokta çifti için bir bitset tuttuğundan boyutu
$$O\!\left(n^2\cdot \left\lceil \frac{n}{64}\right\rceil\right)=O\!\left(\frac{n^3}{64}\right)$$
makine kelimesidir; buna ek olarak \(O(n^2)\) boyutlu kollineerlik tablosu vardır.
Geometrik önişlem tüm \((a,b,p)\) üçlülerini yokladığı için aritmetik olarak \(O(n^3)\) maliyetlidir; fakat sonraki boşluk testlerini bit-paralel hale getirir.
Sabit bir anchor için, \(m\) aday nokta varsa durum uzayı karesel, worst-case geçiş maliyeti ise kübiktir:
$$O(m^3).$$
Pratikte boşluk testleri, yön filtreleri ve incoming-list yapısı birçok geçişi erkenden eler. Dıştaki anchor döngüsü de thread'ler arasında paralelleştirilir.
El problema genera de forma determinista 500 puntos enteros y pide el polígono convexo de área máxima cuyo interior no contiene ningún otro punto generado. En geometría computacional esto se conoce como un mayor agujero convexo.
Los puntos se obtienen de la recurrencia
$$s_0=290797,\qquad s_n=s_{n-1}^2\bmod 50515093,$$
$$t_n=(s_n\bmod 2000)-1000,$$
y luego se forman como
$$P_i=(t_{2i-1},t_{2i})\qquad(1\le i\le 500).$$
El código no enumera polígonos directamente. En su lugar, reduce el problema a pruebas rápidas de vaciedad para triángulos y a una programación dinámica sobre vértices ordenados angularmente.
Los tres primeros puntos son
$$P_1=(527,144),\qquad P_2=(-488,732),\qquad P_3=(-454,-947).$$
El doble del área orientada de este triángulo es
$$\operatorname{cross}(P_1,P_2,P_3)=1684193,$$
por lo que su área ordinaria es \(842096.5\). Esto explica por qué la implementación guarda áreas duplicadas como enteros: con coordenadas enteras, toda área poligonal es un múltiplo entero de \(1/2\).
Para tres puntos \(A,B,C\), definimos
$$\operatorname{cross}(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
Esta cantidad es positiva en un giro a la izquierda, negativa en un giro a la derecha y cero en colinealidad. Geométricamente,
$$|\operatorname{cross}(A,B,C)|=2\,[ABC],$$
donde \([ABC]\) es el área usual del triángulo. Trabajar con área doble evita por completo el redondeo de punto flotante.
Para cada arista dirigida \((a,b)\), el código precomputa el conjunto
$$L(a,b)=\{p:\operatorname{cross}(a,b,p)\gt 0\},$$
es decir, todos los puntos generados que quedan estrictamente a la izquierda de la recta orientada de \(a\) hacia \(b\).
Si el triángulo \((a,b,c)\) está orientado en sentido antihorario, entonces un punto \(p\) está estrictamente en su interior exactamente cuando
$$p\in L(a,b)\cap L(b,c)\cap L(c,a).$$
Por lo tanto, el triángulo es estrictamente vacío si y solo si
$$L(a,b)\cap L(b,c)\cap L(c,a)=\varnothing.$$
Este criterio es ideal para bitsets: la vaciedad se convierte en unas pocas operaciones AND a nivel de palabra.
La palabra “estrictamente” importa. El problema prohíbe puntos en el interior del polígono, pero permite puntos sobre su borde. Por eso se usa \(\gt 0\) y no \(\ge 0\).
Todo polígono convexo tiene un vértice más bajo; si hay empate en la coordenada \(y\), el más a la izquierda es único. Llamemos a ese vértice el ancla \(A\).
Entonces cualquier otro vértice \(v\) del polígono cumple
$$v_y>A_y\quad\text{o}\quad(v_y=A_y\text{ y }v_x>A_x).$$
Así, una vez fijado \(A\), todo polígono admisible que lo usa queda en el semiplano superior respecto de la horizontal por \(A\). El código utiliza exactamente este hecho para construir la lista de candidatos de cada ancla.
Después ordena esos candidatos por ángulo polar alrededor de \(A\). Para un polígono convexo cuyo vértice más bajo-izquierdo es \(A\), este orden angular coincide con el orden en la frontera del polígono.
Fijemos un ancla \(A\), y sean los candidatos ordenados por ángulo
$$v_0,v_1,\dots,v_{m-1}.$$
El estado \(dp[j,k]\) almacena la mayor área doble de una cadena convexa vacía
$$A\to \cdots \to v_j \to v_k$$
cuya última arista es \((v_j,v_k)\). El bloque base es el triángulo \(A,v_j,v_k\), con contribución
$$\Delta(A,v_j,v_k)=\operatorname{cross}(A,v_j,v_k).$$
Si \(\Delta\le 0\), el trío no está orientado en sentido antihorario y no puede formar parte de la cadena.
La transición es
$$dp[j,k]=\max\Big(\Delta(A,v_j,v_k),\max_h\{dp[h,j]+\Delta(A,v_j,v_k)\}\Big),$$
sujeta a tres restricciones:
1. El triángulo \((A,v_j,v_k)\) debe ser estrictamente vacío.
2. El giro en \(v_j\) debe seguir siendo convexo:
$$\operatorname{cross}(v_h,v_j,v_k)\gt 0.$$
3. El segmento \((A,v_j)\) no puede contener otro punto generado en su interior abierto cuando se usa como diagonal interna.
El código precomputa además un indicador booleano has_inner_collinear[a][b] que registra si existe un punto generado en el segmento abierto que une \(a\) con \(b\).
Esto no es un problema para las aristas de la frontera final, porque los puntos sobre la frontera están permitidos. Pero cuando la DP prolonga una cadena a través de \(v_j\), el segmento \((A,v_j)\) se convierte en una diagonal interna del abanico de triangulación. Si otro punto cayera sobre ese segmento abierto, quedaría en el interior del polígono, lo cual está prohibido. Por eso esos estados no se extienden.
Tome cualquier polígono convexo vacío y elija como ancla \(A\) su vértice más bajo-izquierdo. Los demás vértices aparecen en orden angular creciente alrededor de \(A\), y el polígono se triangula como un abanico
$$ (A,v_{i_1},v_{i_2}),\ (A,v_{i_2},v_{i_3}),\ \dots .$$
Como el interior del polígono está vacío, cada uno de esos triángulos es estrictamente vacío. Como el polígono es convexo, los triples consecutivos solo producen giros a la izquierda. Por tanto, todo polígono válido corresponde a una cadena válida de la DP, y su área es exactamente la suma de las contribuciones triangulares.
Recíprocamente, cualquier cadena de la DP que satisface vaciedad, giros a la izquierda y la restricción sobre diagonales internas reconstruye un polígono convexo vacío con ancla \(A\). Así, la DP recorre exactamente la familia factible y maximiza su área.
El código C++ incluye una verificación para los primeros 20 puntos generados. Comprueba que el área doble máxima es
$$2099389,$$
lo que corresponde al área
$$1049694.5.$$
Esto sirve a la vez como prueba de corrección y como recordatorio de que las áreas semienteras aparecen de manera natural.
La implementación tiene cuatro fases principales. Primero genera los 500 puntos a partir de la recurrencia pseudoaleatoria. Segundo, precomputa para cada par dirigido \((a,b)\) tanto el bitset \(L(a,b)\) como el indicador de colinealidad interna sobre el segmento abierto \(ab\). Tercero, para cada ancla \(A\), filtra los candidatos situados arriba/a la derecha de \(A\), los ordena por ángulo y ejecuta la DP de cadenas descrita antes. Finalmente, toma la mejor área doble entre todas las anclas y la imprime con terminación .0 o .5.
Sea \(n=500\). La tabla de bitsets contiene un bitset por cada par ordenado de vértices, de modo que su tamaño es
$$O\!\left(n^2\cdot \left\lceil \frac{n}{64}\right\rceil\right)=O\!\left(\frac{n^3}{64}\right)$$
palabras de máquina, además de una tabla \(O(n^2)\) para los indicadores de colinealidad.
La precomputación geométrica examina cada triple \((a,b,p)\), por lo que su coste aritmético es \(O(n^3)\), aunque a cambio convierte las futuras pruebas de vaciedad en operaciones bit-paralelas muy rápidas.
Para un ancla fijo con \(m\) candidatos visibles, la DP es cuadrática en número de estados y cúbica en el peor caso cuando todas las transiciones son posibles:
$$O(m^3).$$
En la práctica, las pruebas de vaciedad, las restricciones de orientación y el filtrado por aristas entrantes eliminan muchas transiciones. El bucle exterior sobre las anclas se paraleliza entre hilos.
题目先确定性地生成 500 个整点，然后要求在这些点中找出面积最大的“空凸多边形”，也就是内部不包含任何其他生成点的凸多边形。
点集来自递推
$$s_0=290797,\qquad s_n=s_{n-1}^2\bmod 50515093,$$
$$t_n=(s_n\bmod 2000)-1000,$$
并定义
$$P_i=(t_{2i-1},t_{2i})\qquad(1\le i\le 500).$$
代码并不直接枚举所有多边形，而是把问题化成对三角形“是否为空”的快速判定，再在按极角排序的顶点上做动态规划。
前 3 个点是
$$P_1=(527,144),\qquad P_2=(-488,732),\qquad P_3=(-454,-947).$$
这个三角形的有向两倍面积为
$$\operatorname{cross}(P_1,P_2,P_3)=1684193,$$
因此普通面积是 \(842096.5\)。这说明代码为什么把面积存成“二倍面积”的整数：对于整点多边形，面积总是 \(1/2\) 的整数倍。
对三点 \(A,B,C\)，定义
$$\operatorname{cross}(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
它在左转时为正、右转时为负、共线时为零。几何上有
$$|\operatorname{cross}(A,B,C)|=2\,[ABC],$$
其中 \([ABC]\) 表示普通三角形面积。代码用二倍面积来避免浮点误差。
对每条有向边 \((a,b)\)，代码预先计算集合
$$L(a,b)=\{p:\operatorname{cross}(a,b,p)\gt 0\},$$
即所有严格位于从 \(a\) 指向 \(b\) 的有向直线左侧的生成点。
若三角形 \((a,b,c)\) 按逆时针方向定向，则点 \(p\) 严格位于其内部当且仅当
$$p\in L(a,b)\cap L(b,c)\cap L(c,a).$$
因此，该三角形“严格为空”当且仅当
$$L(a,b)\cap L(b,c)\cap L(c,a)=\varnothing.$$
这对 bitset 非常友好：空性判断只需要做若干次按字位的 AND 运算。
这里“严格”很重要。题目禁止的是多边形内部的点，而不是边界上的点，所以判定条件用的是 \(\gt 0\) 而不是 \(\ge 0\)。
任意凸多边形都有唯一的“最低”顶点；如果有多个点具有相同的 \(y\) 坐标，那么其中最左的那个也是唯一的。把这个点记为锚点 \(A\)。
那么多边形的其他顶点都必须满足
$$v_y>A_y\quad\text{或}\quad(v_y=A_y\text{ 且 }v_x>A_x).$$
因此，一旦固定 \(A\)，所有其他候选顶点都位于穿过 \(A\) 的水平线之上的半平面里。代码正是利用这一点，为每个锚点构造候选顶点集。
之后，代码按相对于 \(A\) 的极角对这些候选点排序。对于一个以 \(A\) 为最低且最左顶点的凸多边形，这个极角顺序正好就是其边界上的顶点顺序。
固定锚点 \(A\)，将按极角排序后的候选点记为
$$v_0,v_1,\dots,v_{m-1}.$$
状态 \(dp[j,k]\) 表示如下空凸链
$$A\to \cdots \to v_j \to v_k$$
的最大二倍面积，其中最后一条边是 \((v_j,v_k)\)。基本贡献来自三角形 \(A,v_j,v_k\)：
$$\Delta(A,v_j,v_k)=\operatorname{cross}(A,v_j,v_k).$$
如果 \(\Delta\le 0\)，说明它不是逆时针三元组，自然不能作为合法状态。
转移公式为
$$dp[j,k]=\max\Big(\Delta(A,v_j,v_k),\max_h\{dp[h,j]+\Delta(A,v_j,v_k)\}\Big),$$
但必须同时满足三条约束：
1. 三角形 \((A,v_j,v_k)\) 必须严格为空。
2. 在 \(v_j\) 处必须保持左转，也就是继续保持凸性：
$$\operatorname{cross}(v_h,v_j,v_k)\gt 0.$$
3. 当线段 \((A,v_j)\) 被用作内部对角线时，它的开区间中不能再有其他生成点。
代码额外预计算了布尔值 has_inner_collinear[a][b]，表示在线段 \(ab\) 的开区间上是否存在其他生成点。
对于最终多边形的边界边，这不是问题，因为边界上的点允许存在。但在 DP 从 \(v_j\) 继续扩展时，线段 \((A,v_j)\) 会成为扇形三角剖分中的内部对角线。如果这条对角线的开区间上还有点，那么那个点就会落到多边形内部，这与题意矛盾。因此这些转移必须被禁止。
任取一个空凸多边形，并把它的最低且最左顶点选作锚点 \(A\)。其余顶点按绕 \(A\) 的极角递增排列，而整个多边形可以被扇形剖分为
$$ (A,v_{i_1},v_{i_2}),\ (A,v_{i_2},v_{i_3}),\ \dots .$$
由于多边形内部为空，所以这些三角形都严格为空；由于多边形是凸的，连续三点必然形成左转。因此，每个合法多边形都对应一条合法的 DP 链，而其面积恰好是这些三角形面积贡献之和。
反过来，任何满足“空性 + 左转 + 内部对角线条件”的 DP 链都能重建出一个以 \(A\) 为锚点的空凸多边形。因此，DP 恰好枚举了所有可行对象，并在其中取最大面积。
C++ 代码包含一个对前 20 个生成点的 checkpoint。它验证最大二倍面积为
$$2099389,$$
对应的普通面积是
$$1049694.5.$$
这既是正确性检查，也说明这里出现半整数面积是完全正常的。
实现主要分为四步。第一步，根据伪随机递推生成 500 个点。第二步，对每个有向点对 \((a,b)\) 预处理左侧点集 bitset \(L(a,b)\)，以及开线段 \(ab\) 上是否存在生成点的标记。第三步，对每个锚点 \(A\)，筛出所有位于 \(A\) 上方或同高且更右侧的候选点，按极角排序后执行上面的凸链 DP。最后一步，在所有锚点中取最大的二倍面积，并以 .0 或 .5 的形式输出。
设 \(n=500\)。由于每个有序点对都要保存一个 bitset，bitset 表的规模为
$$O\!\left(n^2\cdot \left\lceil \frac{n}{64}\right\rceil\right)=O\!\left(\frac{n^3}{64}\right)$$
个机器字，再加上一个 \(O(n^2)\) 的共线标记表。
几何预处理要扫描每个三元组 \((a,b,p)\)，所以其算术复杂度是 \(O(n^3)\)，但换来的是后续空性测试的高度位并行化。
对于一个固定锚点，若可见候选点有 \(m\) 个，则 DP 的状态数是二次的，而在最坏情况下转移开销是立方级：
$$O(m^3).$$
在实际运行中，空三角形测试、方向条件以及 incoming 列表会剪掉大量转移。最外层按锚点的循环则由多个线程并行处理。
Задача детерминированно порождает 500 целочисленных точек и просит найти выпуклый многоугольник максимальной площади, внутрь которого не попадает ни одна другая сгенерированная точка. В вычислительной геометрии это называется наибольшей пустой выпуклой дырой.
Точки задаются рекурсией
$$s_0=290797,\qquad s_n=s_{n-1}^2\bmod 50515093,$$
$$t_n=(s_n\bmod 2000)-1000,$$
а затем собираются как
$$P_i=(t_{2i-1},t_{2i})\qquad(1\le i\le 500).$$
Код не перебирает многоугольники напрямую. Вместо этого он сводит задачу к быстрым проверкам пустоты треугольников и динамическому программированию по вершинам, упорядоченным по углу.
Первые три точки равны
$$P_1=(527,144),\qquad P_2=(-488,732),\qquad P_3=(-454,-947).$$
Ориентированная удвоенная площадь этого треугольника равна
$$\operatorname{cross}(P_1,P_2,P_3)=1684193,$$
а обычная площадь, следовательно, равна \(842096.5\). Это сразу объясняет, почему реализация хранит именно удвоенные площади: для целочисленных координат площадь многоугольника всегда кратна \(1/2\).
Для трёх точек \(A,B,C\) вводится
$$\operatorname{cross}(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
Эта величина положительна при левом повороте, отрицательна при правом и равна нулю при коллинеарности. Геометрически
$$|\operatorname{cross}(A,B,C)|=2\,[ABC],$$
где \([ABC]\) — обычная площадь треугольника. Работа с удвоенной площадью позволяет полностью избежать вещественных чисел в DP.
Для каждой ориентированной пары \((a,b)\) код предвычисляет множество
$$L(a,b)=\{p:\operatorname{cross}(a,b,p)\gt 0\},$$
то есть все сгенерированные точки, лежащие строго слева от направленной прямой из \(a\) в \(b\).
Если треугольник \((a,b,c)\) ориентирован против часовой стрелки, то точка \(p\) лежит строго внутри него тогда и только тогда, когда
$$p\in L(a,b)\cap L(b,c)\cap L(c,a).$$
Следовательно, треугольник является строго пустым тогда и только тогда, когда
$$L(a,b)\cap L(b,c)\cap L(c,a)=\varnothing.$$
Это идеально подходит для bitset-представления: проверка пустоты превращается в несколько побитовых операций AND.
Слово «строго» здесь принципиально важно. Условие задачи запрещает точки во внутренности многоугольника, но не запрещает точки на границе. Поэтому используется \(\gt 0\), а не \(\ge 0\).
У любого выпуклого многоугольника есть единственная самая нижняя вершина; если несколько вершин имеют одинаковую \(y\)-координату, то среди них единственная самая левая. Назовём её якорем \(A\).
Тогда любая другая вершина \(v\) многоугольника удовлетворяет условию
$$v_y>A_y\quad\text{или}\quad(v_y=A_y\text{ и }v_x>A_x).$$
Итак, после фиксации \(A\) все остальные вершины лежат в верхней полуплоскости относительно горизонтали через \(A\). Код именно этим фактом пользуется при построении списка кандидатов для каждого якоря.
Затем кандидаты сортируются по полярному углу вокруг \(A\). Для выпуклого многоугольника, у которого \(A\) — нижняя и самая левая вершина, этот угловой порядок совпадает с порядком обхода границы.
Зафиксируем якорь \(A\) и обозначим отсортированные по углу кандидаты через
$$v_0,v_1,\dots,v_{m-1}.$$
Состояние \(dp[j,k]\) хранит максимальную удвоенную площадь пустой выпуклой цепочки
$$A\to \cdots \to v_j \to v_k,$$
у которой последним ребром является \((v_j,v_k)\). Базовый вклад даёт треугольник \(A,v_j,v_k\):
$$\Delta(A,v_j,v_k)=\operatorname{cross}(A,v_j,v_k).$$
Если \(\Delta\le 0\), тройка не ориентирована против часовой стрелки и потому недопустима.
Переход имеет вид
$$dp[j,k]=\max\Big(\Delta(A,v_j,v_k),\max_h\{dp[h,j]+\Delta(A,v_j,v_k)\}\Big),$$
при трёх ограничениях:
1. Треугольник \((A,v_j,v_k)\) должен быть строго пуст.
2. Поворот в \(v_j\) должен оставаться выпуклым:
$$\operatorname{cross}(v_h,v_j,v_k)\gt 0.$$
3. Отрезок \((A,v_j)\), когда он используется как внутренняя диагональ, не должен содержать других сгенерированных точек в своём открытом внутреннем интервале.
Код дополнительно вычисляет булев флаг has_inner_collinear[a][b], который показывает, лежит ли какая-либо сгенерированная точка на открытом отрезке от \(a\) до \(b\).
Для настоящих граничных рёбер итогового многоугольника это не запрещено, потому что точки на границе допускаются. Но когда DP продолжает цепочку через \(v_j\), отрезок \((A,v_j)\) становится внутренней диагональю веерной триангуляции. Если бы на нём лежала ещё одна точка, она оказалась бы внутри многоугольника, что противоречит условию. Поэтому такие переходы запрещаются.
Рассмотрим любой пустой выпуклый многоугольник и выберем его нижнюю-левую вершину как якорь \(A\). Остальные вершины идут в порядке возрастания полярного угла вокруг \(A\), а сам многоугольник раскладывается в веер
$$ (A,v_{i_1},v_{i_2}),\ (A,v_{i_2},v_{i_3}),\ \dots .$$
Поскольку внутренняя область многоугольника пуста, все эти треугольники строго пусты. Поскольку многоугольник выпуклый, последовательные тройки дают только левые повороты. Значит, каждому допустимому многоугольнику соответствует допустимая DP-цепочка, а её площадь равна сумме вкладов этих треугольников.
И наоборот, любая DP-цепочка, удовлетворяющая условиям пустоты, левых поворотов и внутренних диагоналей, восстанавливает пустой выпуклый многоугольник с якорем \(A\). Следовательно, DP перебирает в точности допустимое семейство и максимизирует его площадь.
В C++-коде есть checkpoint для первых 20 сгенерированных точек. Он проверяет, что максимальная удвоенная площадь равна
$$2099389,$$
то есть обычная площадь равна
$$1049694.5.$$
Это одновременно служит тестом корректности и показывает, что полуцелые площади здесь естественны.
Реализация состоит из четырёх основных этапов. Сначала генерируются 500 точек из псевдослучайной рекурсии. Затем для каждой ориентированной пары \((a,b)\) предвычисляются как bitset \(L(a,b)\), так и флаг наличия точки на открытом отрезке \(ab\). После этого для каждого якоря \(A\) строится список точек выше/правее \(A\), он сортируется по углу, и выполняется описанное выше DP по цепочкам. Наконец, берётся лучший результат по всем якорям и печатается в формате .0 или .5.
Пусть \(n=500\). Таблица bitset-ов хранит один bitset для каждой упорядоченной пары вершин, поэтому её размер равен
$$O\!\left(n^2\cdot \left\lceil \frac{n}{64}\right\rceil\right)=O\!\left(\frac{n^3}{64}\right)$$
машинных слов, плюс \(O(n^2)\) памяти на таблицу коллинеарности.
Геометрическая предобработка просматривает все тройки \((a,b,p)\) и потому требует \(O(n^3)\) арифметических операций, зато последующие тесты пустоты становятся очень быстрыми благодаря битовой параллельности.
Для фиксированного якоря с \(m\) видимыми кандидатами пространство состояний квадратично, а наихудшая стоимость переходов кубическая:
$$O(m^3).$$
На практике тесты пустоты, ориентационные ограничения и списки входящих рёбер отсеивают множество переходов. Внешний цикл по якорям распараллеливается между потоками.
تولد المسألة 500 نقطة صحيحة بشكل حتمي، ثم تطلب إيجاد المضلع المحدب الأكبر مساحة الذي لا يحتوي داخله أي نقطة مولدة أخرى. وفي الهندسة الحسابية يسمى هذا أكبر فجوة محدبة فارغة.
تُبنى النقاط من العلاقة التراجعية
$$s_0=290797,\qquad s_n=s_{n-1}^2\bmod 50515093,$$
$$t_n=(s_n\bmod 2000)-1000,$$
ثم تُعرَّف النقاط على الصورة
$$P_i=(t_{2i-1},t_{2i})\qquad(1\le i\le 500).$$
الكود لا يجرب جميع المضلعات مباشرة، بل يحول المسألة إلى اختبارات سريعة لفراغ المثلثات ثم إلى برمجة ديناميكية على رؤوس مرتبة زاويًا.
أول ثلاث نقاط هي
$$P_1=(527,144),\qquad P_2=(-488,732),\qquad P_3=(-454,-947).$$
والمساحة الموجهة المضاعفة لهذا المثلث هي
$$\operatorname{cross}(P_1,P_2,P_3)=1684193,$$
ولذلك تكون مساحته العادية \(842096.5\). وهذا يوضح لماذا يخزن التنفيذ المساحات على صورة مساحة مضاعفة: فإحداثيات الرؤوس صحيحة، ولذلك تكون كل مساحة مضلع من مضاعفات \(1/2\).
لثلاث نقاط \(A,B,C\) نعرّف
$$\operatorname{cross}(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
هذه الكمية تكون موجبة عند الانعطاف يسارًا، وسالبة عند الانعطاف يمينًا، وصفرًا عند الاستقامية. هندسيًا لدينا
$$|\operatorname{cross}(A,B,C)|=2\,[ABC],$$
حيث \([ABC]\) هي المساحة المعتادة للمثلث. لذا فإن استعمال المساحة المضاعفة يزيل الحاجة تمامًا إلى الحساب العشري أثناء البرمجة الديناميكية.
لكل ضلع موجه \((a,b)\) يحسب الكود مسبقًا المجموعة
$$L(a,b)=\{p:\operatorname{cross}(a,b,p)\gt 0\},$$
أي جميع النقاط المولدة التي تقع بدقة إلى يسار المستقيم الموجه من \(a\) إلى \(b\).
إذا كان المثلث \((a,b,c)\) موجَّهًا عكس عقارب الساعة، فإن النقطة \(p\) تقع بدقة داخل هذا المثلث إذا وفقط إذا
$$p\in L(a,b)\cap L(b,c)\cap L(c,a).$$
ومن ثم يكون المثلث فارغًا تمامًا إذا وفقط إذا
$$L(a,b)\cap L(b,c)\cap L(c,a)=\varnothing.$$
وهذا الوصف مناسب جدًا لتمثيل bitset، لأن فحص الفراغ يتحول إلى بضع عمليات AND على مستوى الكلمات.
وكلمة “تمامًا” هنا مهمة: المسألة تمنع النقاط داخل الداخل فقط، لكنها لا تمنع النقاط الواقعة على الحدود. ولهذا السبب يُستخدم الشرط \(\gt 0\) بدلًا من \(\ge 0\).
كل مضلع محدب يملك رأسًا سفليًا وحيدًا؛ وإذا تساوت عدة رؤوس في الإحداثي \(y\)، فإن الأيسر بينها يكون وحيدًا أيضًا. لنسم هذا الرأس المرساة \(A\).
عندئذٍ يجب أن يحقق كل رأس آخر \(v\) من المضلع الشرط
$$v_y>A_y\quad\text{أو}\quad(v_y=A_y\text{ و }v_x>A_x).$$
إذًا بعد تثبيت \(A\)، تقع كل الرؤوس الأخرى في النصف المستوي العلوي بالنسبة إلى الأفق المار عبر \(A\). والكود يستعمل هذه الحقيقة تمامًا عند بناء قائمة المرشحين لكل مرساة.
بعد ذلك ترتب هذه النقاط حسب الزاوية القطبية حول \(A\). وفي مضلع محدب يكون \(A\) فيه هو الرأس الأدنى ثم الأيسر، فإن هذا الترتيب الزاوي يطابق ترتيب الرؤوس على الحد.
لنثبت مرساة \(A\)، ولتكن النقاط المرشحة المرتبة زاويًا هي
$$v_0,v_1,\dots,v_{m-1}.$$
الحالة \(dp[j,k]\) تخزن أكبر مساحة مضاعفة لسلسلة محدبة فارغة من الشكل
$$A\to \cdots \to v_j \to v_k,$$
حيث تكون الحافة الأخيرة هي \((v_j,v_k)\). والمساهمة الأساسية تأتي من المثلث \(A,v_j,v_k\)، ومقدارها
$$\Delta(A,v_j,v_k)=\operatorname{cross}(A,v_j,v_k).$$
إذا كانت \(\Delta\le 0\)، فهذا يعني أن الثلاثي ليس موجهًا عكس عقارب الساعة، وبالتالي لا يصلح كجزء من السلسلة.
صيغة الانتقال هي
$$dp[j,k]=\max\Big(\Delta(A,v_j,v_k),\max_h\{dp[h,j]+\Delta(A,v_j,v_k)\}\Big),$$
ولكن تحت ثلاثة قيود:
1. يجب أن يكون المثلث \((A,v_j,v_k)\) فارغًا تمامًا.
2. يجب أن يبقى الانعطاف عند \(v_j\) محدبًا:
$$\operatorname{cross}(v_h,v_j,v_k)\gt 0.$$
3. عندما تستعمل القطعة \((A,v_j)\) كقطر داخلي، فلا يجوز أن تحتوي في داخلها المفتوح على نقطة مولدة أخرى.
يحسب الكود أيضًا علمًا منطقيًا has_inner_collinear[a][b] يحدد ما إذا كانت هناك نقطة مولدة على القطعة المفتوحة الواصلة بين \(a\) و\(b\).
هذا لا يسبب مشكلة إذا كانت القطعة حدًا نهائيًا للمضلع، لأن النقاط على الحد مسموح بها. لكن عندما تمد البرمجة الديناميكية السلسلة عبر \(v_j\)، تصبح القطعة \((A,v_j)\) قطرًا داخليًا في تشريح مروحي للمضلع. ولو وُجدت نقطة أخرى على هذا القطر المفتوح، لوقعت داخل المضلع، وهذا ممنوع. لذلك تُمنع مثل هذه الانتقالات.
خذ أي مضلع محدب فارغ، واختر رأسه الأدنى ثم الأيسر ليكون المرساة \(A\). عندئذٍ تظهر بقية الرؤوس بترتيب الزاوية المتزايدة حول \(A\)، ويمكن تشريح المضلع إلى مروحة من المثلثات
$$ (A,v_{i_1},v_{i_2}),\ (A,v_{i_2},v_{i_3}),\ \dots .$$
وبما أن داخل المضلع فارغ، فإن كل هذه المثلثات فارغة تمامًا. وبما أن المضلع محدب، فإن كل ثلاثية متتالية تعطي انعطافًا يساريًا. لذلك يقابل كل مضلع صحيح سلسلة صحيحة في البرمجة الديناميكية، وتكون مساحتها مساوية تمامًا لمجموع مساهمات هذه المثلثات.
وبالعكس، فإن أي سلسلة في البرمجة الديناميكية تحقق شروط الفراغ والانعطاف يسارًا والقطر الداخلي تعيد بناء مضلع محدب فارغ ذي مرساة \(A\). ولهذا فإن البرمجة الديناميكية تستعرض بالضبط العائلة الممكنة وتُعظِّم المساحة بينها.
يتضمن كود C++ اختبار تحقق لأول 20 نقطة مولدة. ويؤكد أن أكبر مساحة مضاعفة تساوي
$$2099389,$$
أي أن المساحة العادية هي
$$1049694.5.$$
وهذا مفيد بوصفه اختبار صحة، كما يبين أن ظهور المساحات نصف الصحيحة أمر طبيعي هنا.
يتكون التنفيذ من أربع مراحل رئيسية. أولًا، تُولد النقاط الـ 500 من العلاقة شبه العشوائية. ثانيًا، يُحسب مسبقًا لكل زوج موجه \((a,b)\) كلٌّ من bitset الخاص بالمجموعة \(L(a,b)\) وعلم الاستقامية الداخلية على القطعة المفتوحة \(ab\). ثالثًا، لكل مرساة \(A\) تُستخرج النقاط الواقعة فوق \(A\) أو على مستواه وإلى يمينه، ثم ترتب زاويًا، ثم تُطبَّق برمجة السلاسل المحدبة المذكورة أعلاه. وأخيرًا يؤخذ أفضل مقدار للمساحة المضاعفة بين جميع المراسي، ثم يطبع على صورة تنتهي بـ .0 أو .5.
لنفرض أن \(n=500\). يحتوي جدول الـ bitset على bitset واحد لكل زوج مرتب من الرؤوس، ولذلك يكون حجمه
$$O\!\left(n^2\cdot \left\lceil \frac{n}{64}\right\rceil\right)=O\!\left(\frac{n^3}{64}\right)$$
كلمة آلة، بالإضافة إلى جدول \(O(n^2)\) لعلامات الاستقامية.
المعالجة الهندسية المسبقة تمر على كل ثلاثية \((a,b,p)\)، ولذلك تكلفتها الحسابية \(O(n^3)\)، لكنها تجعل اختبارات الفراغ اللاحقة سريعة جدًا بفضل التوازي على مستوى البتات.
وبالنسبة إلى مرساة ثابتة لها \(m\) مرشحًا مرئيًا، فإن فضاء الحالات تربيعي، أما أسوأ تكلفة للانتقالات فهي تكعيبية:
$$O(m^3).$$
وفي التطبيق العملي، فإن اختبارات الفراغ وقيود الاتجاه وقوائم الحواف الداخلة تزيل عددًا كبيرًا من الانتقالات. كما أن الحلقة الخارجية على المراسي تُوزَّع بالتوازي على عدة خيوط.