ZOJ 3993（2017CCPC秦皇岛站M题）Safest Buildings

本文主要是介绍ZOJ 3993（2017CCPC秦皇岛站M题）Safest Buildings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3993

题目大意：

       最初的防御战是以（0,0）为圆形R为半径的一个圆O1，问你当防御战缩小为最初的圆O1内的一个半径为r的小圆（小圆的圆心随意位置）时，各点的能在小圆内的概率最大的是哪个。

题目思路：

     

AC代码：

#include <string.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
struct Node
{int no;double x,y;double d,val;
}node[105];
bool cmp(Node a,Node b)
{return a.val>b.val||(a.val==b.val&&a.no<b.no);
}
int main()
{int T;int n;double R,r,r1;scanf("%d",&T);while(T--){scanf("%d %lf %lf",&n,&R,&r);r1=R-r;memset(node,0,sizeof(node));for(int i=0;i<n;i++){scanf("%lf %lf",&node[i].x,&node[i].y);node[i].d=sqrt(node[i].x*node[i].x+node[i].y*node[i].y);node[i].no=i+1;if(node[i].d>R){node[i].val=-1;}else if(node[i].d>=r1){node[i].val=min(2*r1,r1-(node[i].d-r));}else{node[i].val+=min(r,r1-node[i].d);node[i].val+=min(r,r1+node[i].d);}}sort(node,node+n,cmp);int sum=0;if(node[0].val!=-1){sum++;for(int i=1;i<n;i++){if(node[i].val==node[0].val)sum++;else break;}}printf("%d\n",sum);if(sum){printf("%d",node[0].no);for(int i=1;i<n;i++){if(node[i].val==node[0].val){printf(" %d",node[i].no);}else break;}printf("\n");}}return 0;
}

这篇关于ZOJ 3993（2017CCPC秦皇岛站M题）Safest Buildings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---