1134 . String of Candied Haws
Description
In the winter of Harbin, there is a delicious food. It is made of candy and haws and always appear as a string on a stick.
When making the string of candied haws, people always want to take as many haws as possible on a stick. Therefore, inspired by this will, let's think about an easier problem. First of all, haws are balls, but we only think about problems on a plane this time, so they can be just considered as circles. Then with different size of haws, we have different size of circles. The stick is modeled as a straight line. And at last we can be a little greedy that there are haws(circles) on the table(plane), and with a stick(line), we can place it at any position to pass as many haws as possible.
Generally speaking, your task is to find a line in the form of Ax+By+C=0 to pass as many circles on a plane as possible and tell this maximum number. It is regarded as "pass" even if the line and the circle has only one common point. Haws cannot intersect each other, neither can circles in this problem. Actually, there will be no common point between any two circles.
Warn: 本題有 specialjudge
Input Format
There will be multiple test cases, each of which starts with a single integer n on the first line, indicating the number of circles. Then n lines follow, each containing three real numbers xi, yi and ri, denoting the center and the radius of the circles seperately.
You can safely assume that n will not exceed 800 and all the real numbers are in the range between 0 and 10000.
A line containing an n equals to 0 indicates the end of the input.
Output Format
For each test case, output the maximum number of circles on the first line and prints the parameters A, B and C of the line.
Note that there is a special judge so that any line satisfying the optimal solution can be accepted. But you should ensure that A2+B2 should not be less than one.
Sample Input 1
5 0 0 1 3 3 1 5 5 1 7 7 1 5 0 1 0
Sample Output 1
4 1 -1 0
Hints
There are five circles in the sample and a line passing the upper four is an optimal solution.
Problem Source
Migrated from old NTUJ.
2009Harbin
Subtasks
| No. | Testdata Range | Score |
|---|