#P5600. Compass and Straightedge Construction
Compass and Straightedge Construction
Compass and Straightedge Construction
You are given a set of known points representing geometric figures. Using only classical ruler and compass constructions, you must construct a required target point within a given number of steps.
You are allowed to perform the following operations:
- Draw a circle with a known point as the center and another known point on the circle. In mathematical notation, this operation draws the circle \( C(P, Q) \) where P is the center and Q is a point lying on the circle.
- Draw a straight line connecting two known points.
Your task is to output a sequence of construction steps. Each step should be one of the following:
- 'C x1 y1 x2 y2': Draw a circle with center at (x1, y1) passing through (x2, y2).
- 'L x1 y1 x2 y2': Draw a line connecting the points (x1, y1) and (x2, y2).
inputFormat
The input consists of several lines:
- The first line contains an integer N (N ≥ 2), the number of initially known points.
- The next N lines each contain two integers representing the coordinates of a known point.
- The following line contains an integer S, the maximum allowed number of construction steps.
- The last line contains two integers representing the coordinates (x, y) of the target point.
outputFormat
If the target point is already one of the known points, output a single line containing the number 0. Otherwise, output a single line containing the word "IMPOSSIBLE". (No additional output is required.)
Note: The outputs are meant to simulate the construction steps. In this problem, a valid construction is defined only if the target point is already available, so if it is not, it is considered impossible to construct within the given steps.
sample
2
0 0
1 0
5
0 0
0