Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Convex Hull and Triangle
Description There are n points and m triangles in the plane. For each triangle, please compute the common area of the triangle and the polygon, which is the convex hull of the given n points:
Input The first line of the input contains an integer number n, which is the number of the points. The follow n lines contain two integer numbers x _{i} and y_{i}, which describes the coordinate of each point. Then the next line contains an integer number m, which is the number of triangles, and there are 6 integer numbers ax_{i}, ay_{i}, bx_{i}, by_{i}, cx_{i} and cy_{i} in each of the follow m lines, which describe the coordinate of vertices in a triangle.
We guarantee that n and m do not exceed 100000. The absolute value of integers appear above is not larger than 20000000. Output For each triangle in input, output the common area of the triangle and the convex hull in a single line. The result should be rounded to nearest integer number. Sample Input 5 0 0 0 2 2 0 2 2 1 1 2 3 3 3 4 4 3 2 0 2 4 0 2 Sample Output 0 2 Source POJ Monthly--2006.06.25, Long Fan |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator