Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Convex Hull and Triangle
Time Limit: 12000MSMemory Limit: 131072K
Total Submissions: 256Accepted: 37Special Judge

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 xi and yi, 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 axi, ayi, bxi, byi, cxi and cyi 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

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

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator