0095. Circles
| Имя входного файла: | circles.in |
| Имя выходного файла: | circles.out |
| Ограничение по времени: | 2 s |
| Ограничение по памяти: | 64 megabytes |
You are given n closed circles lying on the plane. Your task is to find a straight line which intersects the maximal possible number of them.
Input file
The first line of the file contains a single integer 1 ≤ n ≤ 239. The next n lines contain three integers each – xi, yi and ri, where xi and yi are coordinates of the center, and ri is positive radius. All numbers do not exceed 1000 by an absolute value.
Output file
Output in the first line the maximal possible number of circles intersected. Second line must contain the description of straight line in format x1 y1 x2 y2 where (x1, y1) and (x2, y2) are two different points on the line. Output the points' coordinates as precisely as possible. The precision of comparison in the checking program is about 10-9.
Examples:
| circles.in | circles.out |
|---|---|
| 2 0 1 2 3 2 1 | 2 0 1.0 3.000000 2.0000000000E+0000 |
Источник: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Автор: Andrew Lopatin, Nick Durov
Обсудить Отправить решение