AMR10A  Playground
My kid's school cleared a large field on their property recently to convert it into a playing area. The field is polygonal. The school administration decided to separate the field into two areas by building a straight picket fence between the area for the older kids and the area for the younger kids. The fence would go between two nonadjacent vertices of the polygonal field, and given the shape of the field, all such possible fences would lie strictly and entirely within the field.
Naturally, the smaller of the two areas would go to the younger kids. So can you help the school determine what the area of the smaller playarea would be for different fence positions?
INPUT
The first line contains 2 numbers N denoting the number of points in the convex polygon and Q denoting the number of possible locations of straight line fences.
The next N lines contain 2 integers each. The ith line contains the integers xi yi denoting the coordinates of the ith point of the polygon. The points are given in clockwise order.
The next Q lines contain 2 integers a b denoting that a straight line fence is to be drawn connecting a and b.
OUTPUT
Output Q lines one corresponding to each query. For each query, output the area of the smaller region for the corresponding query truncated to 1 decimal place. Always have 1 digit after the decimal place, so if the answer is 1, output it as 1.0 instead.
CONSTRAINTS
4 <= N <= 50000
1 <= Q <= 50000
20,000,000 <= x,y <= 20,000,000
0 <= a < b1
b < N
SAMPLE INPUT
4 2
0 0
0 1
1 2
1 0
1 3
0 2
SAMPLE OUTPUT
0.5
0.5
EXPLANATION
The polygon is given by the points (0,0) (0,1) (1,2) (1,0).
In the first query, we join the points (0,1) and (1,0) which leads to the 2 areas given by (0,0) (0,1) (1,0) and (0,1) (1,2) (1,0). The first triangle has an area of 0.5 and the second triangle has an area of 1. The minimum of these 2 is 0.5.
In the second query, we join the points (0,0) and (1,2) which leads to the 2 areas given by (0,0) (0,1) (1,2) and (0,0) (1,2) (1,0). The first triangle has an area of 0.5 and the second triangle has an area of 1. The minimum of these 2 is 0.5.
hide comments
hackerman97:
20160324 05:11:02
dont use double or any floating value


Dhruv Mullick:
20140816 20:49:44
A small mistake cost me so many WAs 

SanchitK:
20131212 17:46:31
Last edit: 20140623 21:16:02 

triveni:
20121222 03:16:04
At the first sight I thought this question to be too easy.. Then the most irritating one ..I think I have most WA in this question itself..But at last got AC .. :)


Caesum:
20110127 16:48:41
they're the fence, from point 1 to point 3, or point 0 to point 2 

Harish:
20110124 07:07:29
The question is unclear. What are the last Q lines in input arent they coordinates (a,b) ? if not what do they correspond to X or Y coordinate ? How come explanation doesn't include anything to relate 1,3 or 0,2 ? 
Added by:  Varun Jalan 
Date:  20101213 
Time limit:  0.670s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem, ICPC Asia regionals, Amritapuri 2010 