P3442 [POI 2006] NAJ-The Invasion

And so it has come — the Triangles have invaded Byteotia. Byteotia lies on an island, occupying its entire surface. The shape of the island is a convex polygon (i.e., a polygon whose each interior angle is smaller than $180\degree$). A certain number of software factories are located in Byteotia, each of which generates constant gains or losses. The Triangles have decided to occupy such a part of Byteotia which: - is a triangle-shaped area whose vertices are three different vertices of the polygon island, and - brings the largest income, i.e., the sum of all gains and losses generated by factories within the occupied area is maximal. We assume that a factory located on the border or at a vertex of the occupied area belongs to that area. A territory which contains no factory obviously brings zero income. Byteasar, the King of Byteotia, is concerned about the amount of losses the Triangles' invasion could generate. Help him by writing a program that calculates the sum of gains and losses generated by the factories which the Triangles wish to capture. Task. Write a program that: - reads a description of Byteotia's shape and the locations of factories from the input, - determines the maximal sum of gains and losses generated by factories within a triangle whose vertices are three different vertices of the polygon island, - writes the result to the output. Given a convex hull, and a number of resources (factories) inside or on its boundary, each with a weight, choose three different vertices on the convex hull to form a triangle such that the sum of the weights of the resources strictly inside or on the boundary of the triangle is maximized. The number of convex hull vertices $n \le 600$. The number of resources $m \le 10000$.

The first line contains a single integer $n$ ($3 \le n \le 600$), denoting the number of vertices of the polygon island. Each of the following $n$ lines contains two integers $x_j$ and $y_j$ ($-10\ 000 \le x_j, y_j \le 10\ 000$), separated by a single space, denoting the coordinates $x$ and $y$ of consecutive vertices of the island, in clockwise order. The $(n+2)$-nd line contains a single integer $m$ ($1 \le m \le 10\ 000$), denoting the total number of factories. Each of the following $m$ lines contains three integers $x_i'$, $y_i'$ and $w_i$ ($-10\ 000 \le x_i', y_i' \le 10\ 000$, $-100\ 000 \le w_i \le 100\ 000$), separated by single spaces, denoting the coordinates $x$ and $y$ of the $i$-th factory and the gain (for $w_i \ge 0$) or loss (for $w_i < 0$) this factory generates, respectively. Each factory is situated on the polygon island, i.e., within it or on its border. Distinct factories may be located in the same place, i.e., have the same coordinates.

The first and only line should contain a single integer denoting the maximal sum of gains and losses generated by factories within a triangle whose vertices are three different vertices of the polygon island. Notice that it may happen that the outcome is a negative integer.

The correct result is:  Translated by ChatGPT 5