could anyone please tell me the error with my code? It is giving wrong answer.
QUESTION: http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=3109
CODE: http://paste.bradleygill.com/index.php?paste_id=290688
The question is from an ACM-ICPC regional.
QUESTION: http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=3109
CODE: http://paste.bradleygill.com/index.php?paste_id=290688
The question is from an ACM-ICPC regional.
- Type: Precomputation, coordinate geometry
- Cannot find the area on the fly for all Q
- Precompute the area of all polygons with a segment joining 0 and x as end points.
- We can do this by using area of [0,x-1] and area of triangle [0,x-1,x]
- To find area of given polygon we need to add/ subtract the precomputed areas and 1 triangle (how?)
The area[i] stores the area of the polygon which has vertices from 0...i (area[n-1] has the final area)
To find the area of the region from vertices u to v, it is abs(area[v] - area[u]) - area of triangle which has vertices(v, u, 0).
The complexity per test case is O(n + q).