Firestone's blog

Triangles on a grid.
By Firestone, history, 3 years ago, In English

Given $$$n$$$ triangles on the same grid ( more than $$$1$$$ ). Calculate the total area these triangle cover (they may be overlap or not).

Can you help me to approach this problem? Thanks a lot.

Input:

  • The first line represents number $$$n$$$ ( $$$2$$$ ≤ $$$n$$$ ≤ $$$100$$$ ).

  • $$$n$$$ lines follow, each line represent 6 integers — the vertices of the triangle $$$i$$$ ($$$-10^{6}$$$ ≤ $$$x$$$, $$$y$$$ ≤ $$$10^{6}$$$ ).

Output: The area which $$$n$$$ triangles cover on. The difference between your output and the answer must be smaller than $$$10^{-6}$$$ .

Sample input:

3

1 1 5 1 3 3

1 2 5 2 5 6

1 6 5 2 1 2

Sample Output:

15.000000

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Guys :(

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Missing:

  • constraints on $$$n$$$
  • problem source
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I fixed it. Sadly I got this on a paper and doesn't have a source for it.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe it can be solved using Pick's theorem. The points inside are every point inside at least one triangle. The points in the border are the points in the side of at least one triangle and not inside any triangle. At each processed triangle, renew a map with the points in each category. Maybe this is too slow depending on n.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is too slow even with one triangle, since the coordinates are in range $$$-10^6 \ldots 10^6$$$...

    → Reply