#P2229. RaditionProtectionWall

RaditionProtectionWall

A military base in the tested nuclear weapons, an explosion because offailure. In order to prevent nuclear radiation leakage,  it is necessary to establish  a closed house.<o:p></o:p>

<o:p> </o:p>

The closed house  is a convexpolygon in the wall,  will be constructed of  N or fewer connected straight wall segments (3 <= N <=100),  forming a polygon  which contains  the location of thenuclear leak (X0,Y0).  <o:p></o:p>

 

Due to the complex terrain of the military base and the cost , the chief hasobtained from his contractor  a list ofprices for building wall segments at various locations. He could potentially buildN different wall segments, and he knows the coordinates of the endpoints andcost for each of these segments.  The location of the nuclear leak does not lie on any endpoints (X,Y) coordinatesbetween -10000 and 10000,  and  does not lie directly on any of the potentialwall segments.  <o:p></o:p>

 

Determine theminimum-cost set of wall segments that forms a convex polygon containing the location of the nuclear leak.<o:p></o:p>

Input

The input contains K test cases (1<=K<=5). Each test case specifies:
* Line 1: N X0 Y0
* Lines 2..N+1: Five space-separated integers describing a potential wall segment.
the first two integers are the X and Y,coordinates of one endpoint;
the next two integers are the X and Y coordinates of the second endpoint; the last integer is the cost C of building that wall (1 <= C <= 10000).

Output

For each test case generate a single line containing a single integer that is the cost of the cheapest set of walls which form a legal prison or -1 if no such prison can be constructed

Sample Input

1
8 1 1 
0 0 0 3 2
0 0 3 1 2
3 1 2 3 2
0 3 1 2 1
1 2 2 3 1
0 3 2 3 4
1 2 0 0 8
3 1 0 3 8

Sample Output

</p> 
10

HINT

Source

NYOJ

统计

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 主题
  4. Worker 0 in 12ms
  5. Powered by Hydro v4.11.2 Community