Return to Volume I Explanations

 Problem 137 - Polygons, Explanations 

Algorithm

First, look for the points of one polygon that are inside the other polygon. Include them in the intersection.

Then try all segments of polygon 1 with all segments of polygon 2 :

  • If they have a common point, include in the intersection.
  • If they are on the same line, include the two nearest points (out of four) in the intersection.

    Then, compute the convex hull of the intersection to get the intersection area.

    The solution is simply area(P1) + area(P2) - 2 * area(Intersection).

    Trick

    Segment intersection is not line intersection : the intersection point(s) must lie within the convex hull formed by the four points of both segments.

    Input polygons coordinates are given clockwise, but if you wanna, you can reverse them on-the-fly since you already know the number of points.

    Don't forget the line joining the last and the first point of the hull.

    Points and lines are mathematically speaking, convex. Expect them in te input.

    The input WILL be tricky, e.g:

  • Totally overlapping polygons.
  • Not overlapping polygons.
  • side to side polygons.
  • points and lines polygons.
  • one polygon totally included in the other one.
  • Cross-like polygons (Situations where no points of one polygon will be part of the other but there's still an intersection).

    If you are in trouble with the multi-entry input, read my how to read input.

    You can always take a look at my geometry basics.

    Additional Input

    137.in

    Additional Output

    137.out

    Problem

    Given two convex polygons, they may or may not overlap. If they do overlap, they will do so to differing degrees and in different ways. Write a program that will read in the coordinates of the corners of two convex polygons and calculate the `exclusive or' of the two areas, that is the area that is bounded by exactly one of the polygons. The desired area is shaded in the following diagram:

    picture23

    Input

    Input will consist of pairs of lines each containing the number of vertices of the polygon, followed by that many pairs of integers representing the x,y coordinates of the corners in a clockwise direction. All the coordinates will be positive integers less than 100. For each pair of polygons (pair of lines in the data file), your program should print out the desired area correct to two decimal places. The input will end with a line containing a zero (0).

    Output

    Output will consist of a single line containing the desired area written as a succession of eight (8) digit fields with two (2) digits after the decimal point. There will not be enough cases to need more than one line.

    Sample input

    3  5 5  8 1  2 3
3  5 5  8 1  2 3
4  1 2  1 4  5 4  5 2
6  6 3  8 2  8 1  4 1  4 2  5 3
0

    Sample output

    tex2html_wrap_inline34 0.00 tex2html_wrap_inline36 13.50

    where tex2html_wrap_inline38 represents a single space.

    Return to Volume I Explanations