### pratikmoona's blog

By pratikmoona, 13 years ago,
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.
• 0

 13 years ago, # |   +1 Recommendations to solution – Playing Field - 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?)
•  13 years ago, # ^ |   0 That is what I did.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).
•  13 years ago, # ^ |   0 Wait, in what cases would we have to add the precomputed areas?