[POI2006] 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 inner 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, the vertices of which are three different vertices of the polygon-island, 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 in the vertex of occupied area belongs to that area. A territory which contains no factory brings, obviously, a zero income. Byteasar, the King of Byteotia, is concerned by the amount of losses the Triangles' invasion could generate. Help him by writing a programme which shall calculate the sum of gains and losses generated by factories which the Triangles wish to capture. TaskWrite a programme which: reads a decription of Byteotia's shape and the locations of factories from the input file, determines the maximal value of sum of all gains and losses generated by factories within a triangle, whose vertices are three different vertices of the polygon island, writes the outcome to the output file. 给定一个凸包， 并给出凸包内部或边上的若干个资源，每个资源都有权值,现在要在凸包上面选择不同的3个点，使得3个点组成的三角形 内部的资源的权值之和最大。 凸包点个数 $n \le 600$ 资源个数 $m \le 10000$

The first line of the input file contains a single integer $n$ ($3 \le n \le 600$), denoting the number of vertices of the polygon-island. The following $n$ lines of the input contain two integers each $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 a clockwise order. The $(n+2)$-nd line contains a single integer $m$ ($1 \le m \le 10\ 000$), denoting thetotal number of factories. In each of the following $m$ lines there are 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 or on the border of it. Distinct factories may be located in the same place i.e. have the same coordinates.

The first and only line of the output file should contain a single integer denoting the maximal value of sum of all 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.

5
4 1
1 4
8 9
11 5
8 1
4
7 2 3
6 3 -1
4 5 3
9 6 -4

5

the correct result is: