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.