ACM-ICPC 2018 沈阳赛区网络预赛 E. The cake is a lie（最小圆覆盖至少m个点）
题目链接：
https://nanti.jisuanke.com/t/31446
题意：
给你n个半径都为r的圆（n<=300），用一个大圆至少覆盖s个圆，问大圆的最小半径。
思路：
首先发现问题转化为求覆盖n个点中至少s个点的最小圆的半径，再加r就是答案。
于是就可以二分这个大圆的半径R，以每个点为圆心画圆，看是否有区域被覆盖了s次。
具体思路看知乎：https://www.zhihu.com/question/266750532/answer/312982493
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include<bits/stdc++.h>using namespace std;const double eps=1e-8,pi=acos(-1);int sgn(double x){ if (x<-eps) return -1; if (x>eps) return 1; return 0;}double fm(double x){ while(x>pi) x-=2*pi; while(x<-pi) x+=2*pi; return x;}struct P{ double x,y; double len(){ return sqrt(x*x+y*y); } bool operator<(const P &t)const{ return x<t.x||x==t.x&&y>t.y; } bool operator==(const P &t)const{ return x==t.x&&y==t.y; } P operator-(const P &t)const{ return {x-t.x,y-t.y}; } double slope(){ return atan2(y,x); }};double dis(const P &a,const P &b){ return (a-b).len();}const int N=305;P a[N],stk[N*2];bool check(int n,int S,double R){ int ans=0; for (int i=1;i<=n;i++){ int cnt=0; int top=0; for (int j=1;j<=n;j++){ if (a[i]==a[j]){ cnt++; continue; } if (sgn(dis(a[i],a[j])-2*R)>=0) continue; double alpha=acos(dis(a[i],a[j])/2/R); double k=(a[j]-a[i]).slope(); double st=fm(k-alpha),ed=fm(k+alpha); if (st<ed){ stk[++top]={st,1}; stk[++top]={ed,-1}; } else{ cnt++; stk[++top]={ed,-1}; stk[++top]={st,1}; } } sort(stk+1,stk+top+1); if (cnt>=S) return 1; for (int i=1;i<=top;i++){ if (stk[i].y<0) cnt--; else cnt++; if (cnt>=S) return 1; } } return 0;}double solve(int n,int S){ double l=0,r=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) r=max(r,dis(a[i],a[j])); while(r-l>1e-6){ double mid=(l+r)/2; if (!check(n,S,mid)) l=mid; else r=mid; } return l;}int main(){ int t; scanf("%d",&t); while(t--){ int n,S; scanf("%d%d",&n,&S); for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y); double R; scanf("%lf",&R); if (S>n) printf("The cake is a lie.\n"); else printf("%.4f\n",solve(n,S)+R); }} |
评论 (0)
