hihoCoder 1227 The Cats' Feeding Spots"/>
hihoCoder 1227 The Cats' Feeding Spots
The 2015 ACM-ICPC Asia Beijing First Round Online Programming Contest
题意:找出以所给的点为圆心的圆,使得它包含n个点(包括圆心),输出这种圆半径最小值,半径必须是正整数。点不能落在圆上,只能在圆内。
由于m,n的值都很小,所以可以暴力过,计算出每个点到其他点的距离,然后枚举每个点,把它到其他点的距离放进优先队列,再从队列中取足n-1个点(自身已经算1个),注意当把半径+1的时候,考虑会不会把更多的点给包含进来,求出符合要求的最小半径即可。
#include <stdio.h>
#include <queue>
#include <math.h>
#include <string.h>
using namespace std;
struct node
{double x, y;double dis[105];
}spot[105];
int main()
{int t, i, j, m, n, p, minR, tmp;double maxn, minn;bool flag;scanf("%d", &t);while(t--){scanf("%d %d", &m, &n);for(i = 0;i < m;i++) scanf("%lf %lf", &spot[i].x, &spot[i].y);if(m < n){printf("-1\n");continue;}for(i = 0;i < m;i++){p = 0;for(j = 0;j < m;j++)if(i != j)spot[i].dis[p++] = sqrt((spot[i].x-spot[j].x)*(spot[i].x-spot[j].x) + (spot[i].y-spot[j].y)*(spot[i].y-spot[j].y));}minR = 1005;flag = 0;for(i = 0;i < m;i++){priority_queue<double, vector<double>, greater<double> > q;for(j = 0;j < m - 1;j++) q.push(spot[i].dis[j]);j = 1;maxn = 0;while(j < n){maxn = q.top();q.pop();j++;}minn = 1005;if(!q.empty()) minn = q.top();tmp = maxn;tmp++;if(tmp >= minn) continue;flag = 1;minR = tmp<minR?tmp:minR;}if(!flag) printf("-1\n");else printf("%d\n", minR);}return 0;
}
更多推荐
hihoCoder 1227 The Cats' Feeding Spots
发布评论