ZOJ - 3993(思维)

2024-01-03 12:39

文章标签 思维 zoj 3993

本文主要是介绍ZOJ - 3993(思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Safest Buildings

题目传送门
题意:吃鸡游戏，给出初始圈半径以及圈内的建筑，给你下一个圈的半径r(圈被要求在初始圈内)，求最大概率为安全建筑的建筑有那几个。
思路:很简单可以知道，离中心越近越有可能，但事实上在某些范围内概率是相同的当r足够大或者足够小。我们把初始圈叫做大圆，下一个圈为小圆。当2*r大于R时，小圆内切大圆转一圈，可以发现以2*r-R为半径，以原圆心为圆心的圆内的点的安全概率为1即相等。当r<=R-r时，令P圆为小圆内切大圆时圆心围着大圆圆心形成的圆(即小圆圆心的可取范围)，再令小圆内切p圆时圆心形成的圆为q圆，这时我们可以知道，q圆内的点的概率为1，(过一点画无数个半径为r的圆，以这些圆的圆心所形成的圆的面积/p圆的面积即为安全概率)，而q圆内的圆的都可以形成面积相等的圆即安全概率相等。

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <functional>
#define inf 0x7fffffff
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int MAX=1000+10;
const double eps=1e-6;int n,R,r;
struct NODE{int x,y,id;ll dis;
}node[MAX];int cmp(NODE a,NODE b){return a.dis<b.dis;
}int main(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);#endifint T;cin>>T;while(T--){cin>>n>>R>>r;int ans=0,cnt=0;int s[MAX];for(int i=0;i<n;i++){scanf("%d%d",&node[i].x,&node[i].y);node[i].dis=(ll)node[i].x*node[i].x+(ll)node[i].y*node[i].y;node[i].id=i+1;}sort(node,node+n,cmp);if(2*r>=R){int d=2*r-R;d=d*d;for(int i=0;i<n;i++){if(node[i].dis<=d){s[cnt++]=node[i].id;}}}else if(r<=R-r){int d=R-2*r;d=d*d;for(int i=0;i<n;i++){if(node[i].dis<=d){s[cnt++]=node[i].id;}}}if(cnt==0){s[cnt++]=node[0].id;for(int i=1;i<n;i++){if(node[i].dis==node[0].dis){s[cnt++]=node[i].id;}}}sort(s,s+cnt);cout<<cnt<<endl;for(int i=0;i<cnt;i++){if(i==0)cout<<s[i];elsecout<<" "<<s[i];}cout<<endl;}return 0;   
}