hihoCoder 1227 & 2015 北京网络赛 A题

柔情只为你懂 2022-07-17 00:11 135阅读 0赞

#### 题意： ####

给定m个点，然后从这m个点里找到一个点作为圆心，求一个最小的半径使得圆内刚好有n个点，没有压线的点。

#### 思路： ####

预处理一下各点间的距离，暴力枚举圆心，然后找到排序后的第n个判断即可。坑点：n>m的情况要特判一下。

#### code： ####

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    using namespace std;
    
    const int N=105;
    struct  node
    {
        /* data */
        double x,y;
        void read(){
            scanf("%lf%lf",&x,&y);
        }
    }v[N];
    vector<double> vt[N];
    double cal(node A,node B){
        return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
    } 
    
    int main()
    {
        int T;
        scanf ("%d",&T);
        while (T--){
            int m,n;
            scanf ("%d%d",&m,&n);
            for (int i=0;i<=m;i++) vt[i].clear();
            for (int i=0;i<m;i++) v[i].read();
            for (int i=0;i<m;i++){
                for (int j=0;j<m;j++){
                    if (i==j) vt[i].push_back(0);
                    else vt[i].push_back(cal(v[i],v[j]));
                }
            }
            if (n>m){
       puts("-1");continue;}
            int ans=0x3f,f=0;
            for (int i=0;i<m;i++){
                sort (vt[i].begin(),vt[i].end());
                int tt=(int) vt[i][n-1] + 1;
    
                if (tt>=vt[i][n] &&n<m ) continue;
                else {
                    ans=min(ans,tt);
                    f=1;
                }
                //cout<<ans<<endl;
            }
            if (!f) ans=-1;
            cout<< ans<< endl;
        }
    }