本文主要是介绍hihoCoder1227 The Cats' Feeding Spots【暴力】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:
http://hihocoder.com/problemset/problem/1227
题目大意:
给你 M 个点的坐标(二维平面),从这 M 个点中找出 N 个点,使得以这 N 个点中的某一点
为圆心,且半径为整数的圆包含这 N 个点,同时保证圆周上没有点。求这个最小的半径,
如果没有就输出"-1"。
解题思路:
点数最多有 100 个,那么要预先求出 100 个点之间的相互距离,保存在数组 D[][] 中。然
后遍历每个点,对每个点到其他点之间的距离进行排序,判断第 N 个点是否符合要求,并
找出满足要求最小的答案 Ans。
AC代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 110;double X[MAXN],Y[MAXN],D[MAXN][MAXN];double Dist(double x,double y)
{return sqrt(x*x+y*y);
}int main()
{int T,N,M;scanf("%d",&T);while(T--){scanf("%d%d",&M,&N);memset(D,0,sizeof(D));for(int i = 1; i <= M; ++i){scanf("%lf%lf",&X[i],&Y[i]);for(int j = 1; j <= i; ++j)D[i][j] = D[j][i] = Dist(X[i]-X[j],Y[i]-Y[j]);}if(N > M){printf("-1\n");continue;}int Ans = INF;for(int i = 1; i <= M; ++i){sort(D[i]+1,D[i]+1+M);int R = ceil(D[i][N]);if(D[i][N] >= R)R++;if(N < M && R >= D[i][N+1])continue;if(Ans > R)Ans = R;}if(Ans == INF)printf("-1\n");elseprintf("%d\n",Ans);}return 0;
}
这篇关于hihoCoder1227 The Cats' Feeding Spots【暴力】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!