Week--16 CSP模拟 B ZJM要抵御宇宙射线

题目原文

题目描述

据传，2020年是宇宙射线集中爆发的一年，这和神秘的宇宙狗脱不了干系！但是瑞神和东东忙于正面对决宇宙狗，宇宙射线的抵御工作就落到了ZJM的身上。假设宇宙射线的发射点位于一个平面，ZJM已经通过特殊手段获取了所有宇宙射线的发射点，他们的坐标都是整数。而ZJM要构造一个保护罩，这个保护罩是一个圆形，中心位于一个宇宙射线的发射点上。同时，因为大部分经费都拨给了瑞神，所以ZJM要节省经费，做一个最小面积的保护罩。当ZJM决定好之后，东东来找ZJM一起对抗宇宙狗去了，所以ZJM把问题扔给了你~

输入描述

输入第一行一个正整数N，表示宇宙射线发射点的个数
接下来N行，每行两个整数X,Y，表示宇宙射线发射点的位置

输出描述

输出包括两行
第一行输出保护罩的中心坐标x,y 用空格隔开
第二行输出保护罩半径的平方
（所有输出保留两位小数，如有多解，输出x较小的点，如扔有多解，输入y较小的点）
无行末空格

样例输入

5
0 0
0 1
1 0
0 -1
-1 0

样例输出

0.00 0.00
1.00

数据组成

解题思路

分别以所有点为中心与其他点距离平方进行求取，算出剩余点距该点最远的距离。
对上一步求出的最远距离取最小值，如果有多个距离均为最小值，取中心点坐标（输出x较小的点，如扔有多解，输入y较小的点）较小的输出。

实现代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
const int maxn=1010;
long long m[maxn][maxn];
long long c[maxn],d[maxn];
//double x[maxn],y[maxn],p[maxn];
int main(){
    int n,s,t;
    cin>>n;
    memset(m,0,sizeof(m));
    scanf("%lld %lld",&c[1],&d[1]);
    for(int i=2;i<=n;i++){
        scanf("%lld %lld",&c[i],&d[i]);
            for(int j=i-1;j>0;j--){
                m[i][j]=m[j][i]=(c[i]-c[j])*(c[i]-c[j])+(d[i]-d[j])*(d[i]-d[j]);
            }
    }
    /*for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout<<m[i][j]<<" ";
            }
            cout<<endl;
    }*/
    long long ans=1e18,x;
    for(int i=1;i<=n;i++)
    {   
        //cnt=1;
    //  p=0;
        for(int j=1;j<=n;j++){
            if(m[i][j]>m[i][0]){
                m[i][0]=m[i][j];
            }
        
            //m[i][0]=max(m[i][j],m[i][0]); 
        }
        //cout<<ans<<" "<<m[i][0]<<endl;
        if(ans>m[i][0]){
            x=i;
            ans=m[i][0];
        }
        else if(ans==m[i][0]){
            if(c[x]>c[i])
            {
                x=i;
            }
            else if(c[x]==c[i]&&d[x]>d[i]){
                x=i;
            }
        }
    }

    printf("%lld.00 %lld.00\n",c[x],d[x]);
    printf("%lld.00\n",ans);
    return 0;
} 

小结

仔细读题，题中强调以其中一点为中心点，不是求包含所有点的最小圆半径平方。