pratikmoona's blog

Geometry Problem
By pratikmoona, 13 years ago, In English
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.
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
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?)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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).
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Wait, in what cases would we have to add the precomputed areas?
    → Reply