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
Guys :(
Missing:
I fixed it. Sadly I got this on a paper and doesn't have a source for 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.
It is too slow even with one triangle, since the coordinates are in range $$$-10^6 \ldots 10^6$$$...