Problem K
Input: standard input
Output: standard output
Time Limit: 1 second
Memory Limit: 32 MB
Given any two arbitrary polygons,
determine their intersection if it exists.
The
input file contains several sets of input.
Each
set will consist of two polygon description. Each polygon description begins
with a positive integer n corresponding to the number of
vertices, followed by n lines with each line containing
a pair of integer (x,y) representing the x and y coordinates of a
polygon vertex. The vertices will be given in clockwise traversal order and no
two polygon edges would overlap. You should terminate your program if n < 3. You may assume all
integer input is less than or equal to 100.
Output
For each set of input follow the follow
the output description below.
If the two convex polygons do not
intersect then print out 0.
Otherwise, print out the number of intersecting points of the input polygons,
followed by the points. The output must begin with the bottom leftmost point
and must be listed in lexicographical ordering. Your answers must be rounded up
to two digits after the decimal point
3
0 0 0 2 2 24 5 5 5 10 10 10 10 54 1 1 5 1 5 5 1 54 3 0 6 3 3 6 0 30
08 1.00 2.001.00 4.00 2.00 1.00 2.00 5.00 4.00 1.00 4.00 5.00 5.00 2.00 5.00 4.00