HDU 6242 Geometry Problem

/ 0评 / 0

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Alice is interesting in computation geometry problem recently. She found a interesting problem and solved it easily. Now she will give this problem to you :
You are given $ N$ distinct points $ (X_i,Y_i)$ on the two-dimensional plane. Your task is to find a point $ P$ and a real number $ R$, such that for at least $ ⌈\frac{N}{2}⌉$ given points, their distance to point $ P$ is equal to $ R$.

Input

The first line is the number of test cases.
For each test case, the first line contains one positive number $ N(1≤N≤10^5)$.
The following $ N$ lines describe the points. Each line contains two real numbers $ X_i$ and $ Y_i (0≤|X_i|,|Y_i|≤10^3) $indicating one give point. It's guaranteed that $ N$ points are distinct.

Output

For each test case, output a single line with three real numbers $ X_P,Y_P,R$, where $ (X_P,Y_P)$ is the coordinate of required point $ P$. Three real numbers you output should satisfy $ 0≤|X_P|,|Y_P|,R≤10^9$.

It is guaranteed that there exists at least one solution satisfying all conditions. And if there are different solutions, print any one of them. The judge will regard two point's distance as $ R$ if it is within an absolute error of $ 10^{−3}$ of $ R$.

Sample Input

Sample Output

#Source

2017中国大学生程序设计竞赛-哈尔滨站-重现赛(感谢哈理工)

题解

随机化
题意:给出一系列点,问一点P为圆心R为半径的圆,至少ceil(N/2)的点在圆上
思路:三点定圆,$ (\frac{1}{2})^3=\frac{1}{8}$的概率随机正确,当随机的次数够多(大约100次)正确率可以接近$ 99.99999999$%
注意特判4点与2点情况

Code

发表评论

电子邮件地址不会被公开。 必填项已用*标注