Convex Painter
------ -------
Iffy the `artist' has developed a new drawing machine
to help him paint abstract art. The art is to consist
of a set of nested convex polygons, the outlines of
which the machine is to draw. Then Iffy will paint
the areas bounded by consecutively nested polygons
various different colorful colors.
More specifically, the input to the machine is a convex
polygon on the canvas and a sequence of points randomly
chosen to be somewhere inside the canvas. The machine
then chooses a subsequence of the randomly chosen points
that together are the vertices of a new convex polygon
that is inside the input polygon. It does this by
accepting or rejecting each random point as it is
presented. The first two random points that are inside
the input polygon are always accepted. Thereafter the
machine accepts a point P if and only if:
(1) P is inside the input polygon, and NOT on the
boundary of that polygon.
(2) If P1 and P2 are the first two accepted points in
order of acceptance, and Q1 and Q2 are the last two
accepted points in order of acceptance, then:
(2a) P is to the right of the directed line from
Q1 to Q2.
(2b) P1 is to the right of the directed line from
Q2 to P.
(2c) P2 is to the right of the directed line from
P to P1.
Given this, if the machine accepts at least 3 points,
the accepted points in order of acceptance will be
the vertices of a convex polygon in clockwise order.
If Iffy does not like the result, he will reject it
and ask the machine to try again. But this is outside
the purview of this problem.
Input
-----
A sequence of test cases. Each test case begins with
a line containing the test case name. Following are
exactly two `point sequence lines', each of the form
K X1 Y1 X2 Y2 ... XK YK
where K >= 3 is an integer and (X1,Y1), (X2,Y2), ...
(XK,YK) are K points in the plane. The first of the
two lines defines the input convex polygon by giving
its vertices in clockwise order. The second of the
two lines defines the sequence of random points on the
canvas.
The X's and Y's are integers. If the values of K for
the two lines in a test case are designated K1 and K2,
then
3 <= K1, K2 <= 1,000
sum K1*K2 over all test cases <= 1,000,000
-10,000 <= X,Y <= +10,000
The test case name line has at most 80 characters.
Input ends with an end of file.
Output
------
For each test case, first an exact copy of the test case
name line. Then just one point sequence line, formatted
as above, that gives the sequence of accepted points, in
order of acceptance.
The input will be such that at least 3 points will be
accepted, so the sequence of accepted points will be the
vertices of a convex polygon.
Display
-------
The input and output can be displayed in X-Windows or
printed by the commands
display_canvas sample.in [sample.test]
print_canvas sample.in [sample.test]
where sample.test is the output file corresponding to
sample.in, and these files can be replaced by any
test case input file and its corresponding output.
The output file can be omitted in which case only the
input will be displayed.
Sample Input
------ -----
-- SAMPLE 1 --
5 0 0 1 10 10 8 11 4 5 -3
9 2 2 2 11 4 4 5 5 6 4 7 8 8 2 5 1 1 1
-- SAMPLE 2 --
6 3 -9 -9 -4 -5 0 -1 3 5 7 9 -4
10 2 -9 -6 -3 -3 -9 3 -2 4 -2 4 -8 2 -5 -7 -4 -1 1 3 5
Sample Output
------ ------
-- SAMPLE 1 --
5 2 2 4 4 6 4 8 2 5 1
-- SAMPLE 2 --
5 -6 -3 3 -2 4 -2 4 -8 -7 -4
File: convexpainter.txt
Author: Bob Walton
Date: Sun Oct 13 21:02:34 EDT 2019
The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.