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 – x_i, y_i and r_i, where x_i and y_i are coordinates of the center, and r_i 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 x₁ y₁ x₂ y₂ where (x₁, y₁) and (x₂, y₂) 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

Обсудить       Отправить решение



Версия для печати