0166. Circles On The Toral Screen
| Имя входного файла: | circles.in |
| Имя выходного файла: | circles.out |
| Ограничение по времени: | 1 s |
| Ограничение по памяти: | 64 megabytes |
Peter's computer is attached to screen 256*256. This screen has very unusual form. It is a tore! That's so beatiful! If his window is too large to be displayed, it just covers itself and the operating system allows to switch between the first part of the window and the second one.
Now Peter is writing a graphical editor for this screen. He decided to use the screen form in a very special way in his editor. Of course, if we go, for example, from point (255, 255) to the right direction, we will come to point (0, 255). So Peter decided to allow any possible integer values of coordinates so he will be able to draw very long curves without any checks as if he would have a very-very long screen. So, getting point coordinates (x, y), the editor always take them modulo 256. Note that it must use the positive remainder, for example, point (-239, -17) corresponds to the physical point (17, 239).
Now Peter has decided to implement circles drawing procedure in his editor. He thought for a very long time about it. Now he knows that the representation of the circle on the (usual flat, but possibly very-very long) screen is a non-empty set of points (x, y) with two conditions satisfied:
- Exactly two of eight neighbours of any fixed point from this set (x, y) belong to this set.
- The second condition is much harder to explain. Let us fix any point from the set (x, y). Denote with M the set of all its eight neighbours except the neighbours that belong to the representation. Let us include the point (x, y) itself to M also, so M will always contain seven points. The point (x, y) must be the true nearest point to the circle from this set. That is, the point (x, y) gives a true minimum to the absolute value of the difference of the Euclid distance of the point to the center of the circle and the radius of the circle (i. e. the function |sqrt((x-x0)2+(y-y0)2)-r| for the point (x, y) must be less than the value of this function for all other points of M, where (x0, y0) are coordinates of the center of the circle).
Now Peter asks you to help him to implement the creation of this representation to display it on his toral screen in his editor. The screen is empty at the beginning. Your program will read descriptions of the circles from the input file and draw them on the screen. If it is not possible to build representation of any of the given circles, your program must detect this fact.
Input file
The first line of the input file contains the number of circles to be drawn 1 ≤ K ≤ 1000. The next K lines contain the circles descriptions. Each circle is described by three numbers x, y and r – coordinates of the center and the radius of the circle. Coordinates are integers with absolute value not greater than 108, and radius is a non-negative integer which does not exceed 107. Also it is always guaranteed that the total sum of all radii does not exceed 107.
Output file
If there were circles which do not have representation, the first line must contain message "Circles without representation were detected!". Then l lines must follow, each of which must correspond to one circle without representation in order they appear in input file (l is the total number of circles without representation). These lines must have format "Unable to build circle x y r". All messages are to be displayed without quotes.
In the other case, the file must contain the contents of the screen. The screen is represented by 256 lines of 256 characters each. You must use color (i mod10) for i-th circle. For example, first circle from the input file must be displayed with the color `1', hundredth – with color `0', and two hundred thirty ninth – with `9'. The circles must be drawn in order they appear. For pixels which were left empty, use symbol `.'. Note that x coordinate grows right and the y coordinate grows down.
The dots in ends of lines of the example output are removed for paper saving purposes. Your program must output lines with exact length of 256 characters.
Examples:
| circles.in | circles.out |
|---|---|
| 2 5 2 3 10 10 8 | ...1...1 ..1.....1 ..1.....22222 ..1...221....22 ...1.2.1.......2 ....211.........2 ...2.............2 ...2.............2 ..2...............2 ..2...............2 ..2...............2 ..2...............2 ..2...............2 ...2.............2 ...2.............2 ....2...........2 .....2.........2 ......22.....22 ........22222 236 lines of 256 dots follow ....111 |
Источник: Petrozavodsk Summer 2003. KOTEHOK's Contest, Sunday, August 31
Автор: Andrew Lopatin
Обсудить Отправить решение