[TopCoder - 12244 SRM 559 Round1 Div1] CircusTents

Posted on Edited on In

[TopCoder - 12244 SRM 559 Round1 Div1] CircusTents

小而精的计算几何题

题目大意：有 \(n\) 个实心圆（不能从内部经过）

在第一个圆上选出一个点，使得从其他任意圆上到达它的最小距离 最大

分析：要最小值最大，显然可以想到二分答案

不能穿过其他圆这一条件让计算答案变得十分困难，但是可以发现，如果路径经过了一号圆以外的圆

那么从路径与该圆的交点直接过去的距离一定更近

也就是说，可以把 距离 看做 可以穿过一号圆以外的圆 的距离

考虑从一个圆 \(O\) 到达一号圆上的某一点 \(X\) 的最小距离，大致可以成两种情况

  1. \(OX\) 连线不穿过一号圆，那么可以直接走 \(OX\) 连线
QQ截图20201102162335.png

最优路径就是绿色线

2.先走一条切线，然后绕着圆周走一段

QQ截图20201102162651.png

其中 \(Y\) 是 \(O\) 点对于一号圆的切线的切点，绿色线+圆弧是最优路径

那么二分答案 \(mid\) 之后，可以发现满足距离 \(\ge mid\) 的选点位置是一段圆弧，可以从角度取交集判断是否有解

实现上，可以先把一号圆平移到远点

然后对于其他的圆，按照角度范围是否在切线内部可以分类讨论

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
#include<bits/stdc++.h>
using namespace std;
typedef double db;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

const int N=110;
const db eps=1e-10,Pi=acos(-1),D=2*Pi;

int n;
struct Cir{
    int x,y,r;
}A[N];

db X[N],Y[N],H[N];
int C,S[N];
db Norm(db x){ return x<0?x+D:x; }
int I(db x){ return lower_bound(H+1,H+C+1,x)-H; }

int Check(db L){
    memset(S,0,sizeof S);
    H[1]=0,H[C=2]=D;
    rep(i,1,n) {
        db dis=A[i].x*A[i].x+A[i].y*A[i].y;
        db t=sqrt(dis-A[0].r*A[0].r)-A[i].r;
        //t为走过切线的距离
        dis=sqrt(dis);
        if(dis-A[0].r-A[i].r>=L){ X[i]=0,Y[i]=D; continue; }
        db l,r;
        if(t>=L) {
            // 说明范围在切线位置以内
            // 此时，满足d=dis((x0,y0),A[i].O)-A[i].r>=L
            db a=dis,b=A[0].r,c=L+A[i].r;
            db co=(a*a+b*b-c*c)/(2*a*b);
            //余弦定理
            db x=acos(co),y=atan2(A[i].y,A[i].x);
            l=y+x,r=y-x+D;
        } else {
            db d=acos(A[0].r/dis);
            db x=atan2(A[i].y,A[i].x);
            db y=(L-t)/A[0].r+d;
            // 圆弧长度/半径得到圆弧弧度
            if(y>Pi) return 0; // 特判一下全部覆盖的情况
            l=x+y,r=x-y+D;
        }
        // 求 [l,r] 的交
        if(r>D) l-=D,r-=D;
        if(r<=0) l+=D,r+=D;
        H[++C]=Norm(X[i]=l),H[++C]=Y[i]=r;
    }

    sort(H+1,H+C+1);
    rep(i,1,n) {
        if(X[i]>=0) S[I(X[i])]++,S[I(Y[i])]--;
        else S[I(0)]++,S[I(Y[i])]--,S[I(X[i]+D)]++,S[I(D)]--;
    }
    // 暴力求交
    rep(i,1,C) if((S[i]+=S[i-1])==n) return 1;
    return 0;
}

class CircusTents {
    public:
        double findMaximumDistance(vector <int> _x, vector <int> _y, vector <int> _r) {
            n=_x.size()-1;
            rep(i,0,n) A[i]=(Cir){_x[i]-_x[0],_y[i]-_y[0],_r[i]};

            db l=0,r=1e5;
            while(r-l>eps) {
                db mid=(l+r)/2;
                if(Check(mid)) l=mid;
                else r=mid;
            }
            return l;
        }
};