27790번 - Napkin Folding 서브태스크스페셜 저지다국어채점 준비 중

Chalk has been actively traveling the world with his friends taking pictures in all the coolest places. Most recently, he made his way to Europe, where he studied the history of napkin folding. Ever since, Chalk has been collecting a wide variety of napkins to practice the art of napkin folding.

Chalk's napkins can be defined as simple polygons. A simple polygon is a polygon in which no edges intersect except for adjacent edges which meet at their shared vertex. Each vertex of the polygon is on exactly two edges.

Chalk folds his napkins by first drawing a folding pattern on them. A folding pattern is a set of K-1 line segments which are drawn on the napkin. Each line segment connects two points with rational coordinates on the border of the polygon defining the napkin and is fully contained in the polygon. No two line segments in a folding pattern may touch or overlap, except possibly at common endpoints. A folding pattern of K-1 line segments splits the napkin into K polygonal regions. Two points are in the same region if there exists some continuous line (not necessarily straight) between them which does not intersect any edge of the polygon or any line segment in the folding pattern — even at endpoints.

Chalk is only interested in neat folding patterns. A folding pattern is neat if any two regions that are adjacent to the same folding line segment F are symmetric with respect to F. This means that folding the napkin along that line segment would result in the two regions lining up perfectly.

The following picture illustrates a neat folding pattern with K=8 regions.

Chalk has been successfully folding his collection of napkins using neat folding patterns. But he has some napkins in his collection that he has not been able to find a neat folding pattern for. For each of those napkins, Chalk needs your help to find a neat folding pattern with K regions or determine that no such neat folding pattern exists.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing two integers N and K: the number of points in the polygon defining Chalk's napkin and the number of regions to split the napkin into with a neat folding pattern containing K-1 line segments.

The polygon defining the napkin is represented as a list of the N vertices, as encountered when traveling along the perimeter of the polygon in the clockwise direction, with the first vertex being chosen arbitrarily. The next N lines represent that list. The i-th of these contains two integers X_i and Y_i, indicating that the i-th point is located at (X_i, Y_i) in two-dimensional space.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is POSSIBLE if it is possible to make a neat folding pattern with K regions and IMPOSSIBLE otherwise.

If it is possible to make a neat folding pattern with K regions, output K-1 more lines listing the segments of a neat folding pattern with K regions, in any order. Each line should represent a different segment as Ax Ay Bx By, where (Ax, Ay) and (Bx, By) are the two endpoints of the segment, in any order. Each of Ax, Ay, Bx, and By should be in the form N/D where N and D are positive integers (written with no leading zeroes) sharing no common prime factors, and representing the rational number N/D. There must be no whitespace between N and /, or between / and D.

• 1 ≤ T ≤ 100.
• 3 ≤ N ≤ 200.
• 1 ≤ X_i ≤ 1000, for all i.
• 1 ≤ Y_i ≤ 1000, for all i.
• The N points are given in clockwise order.
• No two adjacent edges of the polygon are collinear.
• The polygon is a simple polygon with strictly positive area.
• No two edges intersect except for adjacent edges at their shared endpoint.

• K = 2.

• 2 ≤ K ≤ 10.

Note: Sample 2 is not valid for Test set 1. Only Sample 1 will be tested prior to running Test set 1 (the same way samples normally are).

For Sample Case #1, a neat folding pattern with K=2 can be drawn using any of the 4 dashed lines:

For Sample Case #2, a neat folding pattern with K=2 can be drawn as follows:

For Sample Case #3, there are no neat folding patterns:

For Sample Case #4, there are two possible neat folding patterns with K=2:

For the test set 2 sample case, a neat folding pattern with K=8 can be drawn as follows: