#P5600. Compass and Straightedge Construction

    ID: 18830 Type: Default 1000ms 256MiB

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:

  1. 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.
  2. 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).
The input guarantees that the target point is among the initial known points or not constructible within the allowed steps. In the case the target point is already present in the set of known points, no construction step is needed and you should output 0. Otherwise, output the word "IMPOSSIBLE".

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