欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(HDU):6242 Geometry Problem (几何水题)

程序员文章站 2022-04-02 16:58:57
...

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6242

Geometry Problem

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 (Xi,Yi) on the two-dimensional plane. Your task is to find a point P and a real number R, such that for at least ⌈N2⌉ 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≤105).

The following N lines describe the points. Each line contains two real numbers Xi and Yi (0≤|Xi|,|Yi|≤103) 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 XP,YP,R, where (XP,YP) is the coordinate of required point P. Three real numbers you output should satisfy 0≤|XP|,|YP|,R≤109.

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

1
7
1 1
1 0
1 -1
0 1
-1 1
0 -1
-1 0

Sample Output

0 0 1

题目大意

给出n个点,判断是否存在任意三个点组成的包含至少n/2个点的圆。

解题方法:

将所有点保存在一个集合里面,每次随机三个点看是否能够组成一个圆(三点共线则不成圆),如果能,则判断所有点是否有一半以上在所得的圆上即可。
三点共线判定:https://blog.csdn.net/sinat_38972110/article/details/82115637
此题数据不够严,不用用斜率来判断也能AC。

代码展示(可能有些不足):

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <cmath>
using namespace std;

const double eps=1e-3;

struct P
{
    double x,y;
} sb[100005];

P Yuanxin(P a,P b,P c)     //(已知三点求圆心坐标)
{
    P q;
    q.x=((c.y-a.y)*(c.y-b.y)*(b.y-a.y)+(a.x*a.x-b.x*b.x)*(c.y-a.y)-(a.x*a.x-c.x*c.x)*(b.y-a.y))/(2*((c.y-a.y)*(a.x-b.x)-(a.x-c.x)*(b.y-a.y)));
    q.y=((c.x-a.x)*(c.x-b.x)*(b.x-a.x)+(a.y*a.y-b.y*b.y)*(c.x-a.x)-(a.y*a.y-c.y*c.y)*(b.x-a.x))/(2*((c.x-a.x)*(a.y-b.y)-(a.y-c.y)*(b.x-a.x)));
    return q;
}
int main()
{
    int t;
    cin>>t;
    srand((unsigned int)time(NULL));
    /*
    srand函数可以是每次随机的值不同(包含在 stdlib.h 头文件中)
    */
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i = 0 ; i < n ; i++)
            scanf("%lf%lf",&sb[i].x,&sb[i].y);
        if(n == 1 || n == 2)
        {
            printf("%lf %lf %lf\n",sb[0].x + 1,sb[0].y,1.0);
            continue;
        }
        if(n == 3 || n == 4)
        {
            printf("%lf %lf %lf\n",(sb[0].x+sb[1].x)/2,(sb[0].y+sb[1].y)/2,sqrt(((sb[0].x-sb[1].x)*(sb[0].x-sb[1].x))+((sb[0].y-sb[1].y)*(sb[0].y-sb[1].y)))/2);
            continue;
        }
        while(1)
        {
            int a = rand()%n;
            int b = rand()%n;
            int c = rand()%n;
            if(a == b || a == c || b == c)
                continue;
            double x1,x2,x3,y1,y2,y3;
            x1=sb[a].x;x2=sb[b].x;x3=sb[c].x;
            y1=sb[a].y;y2=sb[b].y;y3=sb[c].y;
            if((x1 == x2 && x2 == x3) || (y1 == y2 && y2 == y3))
                continue;
            P yuanxin = Yuanxin(sb[a],sb[b],sb[c]);
            double r = sqrt(((sb[a].x-yuanxin.x)*(sb[a].x-yuanxin.x))+((sb[a].y-yuanxin.y)*(sb[a].y-yuanxin.y)));
            int sum=0;
            for(int i = 0 ; i < n ; i++)
            {
                if(fabs(sqrt(((sb[i].x - yuanxin.x) * (sb[i].x - yuanxin.x)) + ((sb[i].y - yuanxin.y) * (sb[i].y - yuanxin.y))) - r) <= eps)
                    sum++;
            }
            if(2 * sum >= n)
            {
                printf("%lf %lf %lf\n",yuanxin.x,yuanxin.y,r);
                break;
            }
        }
    }
    return 0;
}
相关标签: 几何水题