离大海最远点在哪里？
http://218.5.5.242:9014/problem.asp?id=1678
题目描述
遥远的海上有一座岛屿，这个岛屿的轮廓是一个凸多边形，把边视为岛屿的海岸线。当地的居民想要在岛屿上找一地点使其到大海的距离最远，这地点应在哪里？
岛上居民们习惯地把岛上某个点到岛屿的各条海岸线（即各边）距离中最小者看成该点到大海的距离。如下图所示，点O到大海的距离为min{j,k,l,m,n}=j,其中j,k,l,m,n分别为O到AB，BC，CD，DE，EA的距离。
现在，给您N个点来描述这个凸多边形海岛，岛上的居民请您帮他们计算出岛上距离大海最远的点到大海的距离。
输入
第一行一个正整数N(N<=200000)，表示凸N边形的边数，以下N行每行两个整数(xi,yi)，表示凸N边形的每个点的坐标，坐标按逆时针方向给出，且|xi|,|yi|<=1011.
输出
一行一个实数d，表示所求距离。d保留6位小数。答案保证c/c++的double和pascal的extended可存。
样例输入
4 1 1 0 1 0 0 1 0
样例输出
0.500000
提示
数据范围：N<=200000，|xi|,|yi|<=1011
题解
算法1：二分将半平面推进，判交集是否为空
但是使用半平面交做法的话，不仅答案精度不够，还有可能超时
只能通过部分数据
算法2：实际上。我们只要知道最后凸多边形面积变为0的时候，所有半平面向内平移了多少距离，那么，这个距离就是答案。
凸多边形减小的过程，实质是一条边一条边减少，而且减少的那条边对小凸多边形的控制可以由其相邻的两条边取代，即每过一段时间，就减少了一条边的约束，直到最后剩下两条边。那么，我们只要知道在什么时刻，减少了哪条边就可以了。因此，对于每一条边i，我们维护其在什么时刻被相邻的两条边取代，记为ti。
1.这条边相邻两边平行，则ti为两边距离的一半
2.这条边相邻两边不平行，ti为其相邻两角的角平分线交点到它的距离
那么，每次对于小凸多边形，在所有边中取最小的ti，将所对应的边删除，并维护相邻的两条边被删除的时间，就可以了。
实现使用堆+双向链表
半平面交
|
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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
#include<set> #include<map> #include<ctime> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define rad 100000000 #define ll long long #define eps 1e-12 #define pi acos(-1) using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; struct P{ double x,y; P(double _x=0,double _y=0){ x=_x;y=_y; } friend P operator-(P a,P b){ return P(a.x-b.x,a.y-b.y); } friend double operator*(P a,P b){ return a.x*b.y-a.y*b.x; } }p[200005]; struct L{ P a,b;double angle; friend bool operator<(L a,L b){ if(fabs(a.angle-b.angle)<1e-8)return (a.b-a.a)*(b.b-a.a)>0; return a.angle<b.angle; } friend P operator*(L a,L b){ double k1,k2,t; k1=(a.a-b.b)*(b.a-b.b),k2=(b.a-b.b)*(a.b-b.b); t=k1/(k1+k2); return P(a.a.x+(a.b.x-a.a.x)*t,a.a.y+(a.b.y-a.a.y)*t); } friend L move(L a,double d){ L ans; double t=a.angle+pi/2; ans.a=P(a.a.x+d*cos(t),a.a.y+d*sin(t)); ans.b=P(a.b.x+d*cos(t),a.b.y+d*sin(t)); ans.angle=a.angle; return ans; } }ini[200005],l[200005],q[200005]; bool rep(L a,L b,L now) { P t=a*b; return (t-now.a)*(now.b-now.a)>0; } int hpi() { int cnt=0; for(int i=1;i<=n;i++) { if(fabs(l[i].angle-l[cnt].angle)>eps)cnt++; l[cnt]=l[i]; } int L=1,R=0; q[++R]=l[1];q[++R]=l[2]; for(int i=3;i<=cnt;i++) { while(L<R&&rep(q[R-1],q[R],l[i]))R--; while(L<R&&rep(q[L+1],q[L],l[i]))L++; q[++R]=l[i]; } while(L<R&&rep(q[R-1],q[R],q[L]))R--; while(L<R&&rep(q[L+1],q[L],q[R]))L++; return R-L+1; } int main() { n=read(); for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(); p[n+1]=p[1]; for(int i=1;i<=n;i++) { ini[i].a=p[i],ini[i].b=p[i+1]; ini[i].angle=atan2(p[i+1].y-p[i].y,p[i+1].x-p[i].x); } double L=0,R=1000000000000LL,mid; for(int i=1;i<=100;i++) { mid=(L+R)/2; for(int j=1;j<=n;j++) l[j]=move(ini[j],mid); if(hpi()>=3)L=mid; else R=mid; } printf("%.6lf",L); return 0; } |
pq+双向链表
|
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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define abs(x) ((x)>0?(x):-(x)) #define eps 1e-13 #define LL long long #define LB long double #define pa pair<LB,int> #define mp(x,y) make_pair(x,y) using namespace std; LL read() { LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int pre[200005],nxt[200005]; bool del[200005]; LB ans; struct P{ LB x,y; friend LB operator*(P a,P b){ return a.x*b.y-a.y*b.x; } friend P operator+(P a,P b){ return (P){a.x+b.x,a.y+b.y}; } friend P operator-(P a,P b){ return (P){a.x-b.x,a.y-b.y}; } friend P operator*(P a,LB b){ return (P){a.x*b,a.y*b}; } friend LB dis(P a){ return sqrt(a.x*a.x+a.y*a.y); } }p[200005]; void print(P a) { printf("(%.3Lf,%.3Lf)",a.x,a.y); } struct L{ P a,b; friend P cp(L a,L b){// crossover point double k1,k2,t; k1=(a.a-b.b)*(b.a-b.b),k2=(b.a-b.b)*(a.b-b.b); t=k1/(k1+k2); return (P){a.a.x+(a.b.x-a.a.x)*t,a.a.y+(a.b.y-a.a.y)*t}; } }l[200005]; L ab(P a,P b,P c){ // angle a,b,c // angular bisector LB l1=dis(a-b),l2=dis(b-c); a=b+(a-b)*(l2/l1); P t=a+c;t.x/=2;t.y/=2; return (L){b,t}; } LB dis(L l,P a){ return abs((l.b-l.a)*(a-l.a))/dis(l.a-l.b); } priority_queue<pa,vector<pa>,greater<pa> >pq; void add(int x) { L ll=l[pre[x]],rl=l[nxt[x]]; LB t; if(fabs((ll.b-ll.a)*(rl.b-rl.a))<eps) t=dis(ll,rl.b)/2; else { L l1=ab(ll.a,ll.b,l[x].b); L l2=ab(l[x].a,rl.a,rl.b); if(fabs((l1.b-l1.a)*(l2.b-l2.a))<eps)t=1e20; else { P p=cp(l1,l2);t=dis(l[x],p); } } pq.push(mp(t,x)); } int main() { n=read(); for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(); p[n+1]=p[1]; for(int i=1;i<=n;i++) l[i]=(L){p[i],p[i+1]}; for(int i=1;i<=n;i++) pre[i]=i-1,nxt[i]=i+1; pre[1]=n;nxt[n]=1; for(int i=1;i<=n;i++)add(i); for(int i=1;i<=n-2;i++) { int id=pq.top().second; while(del[id]) { pq.pop(); id=pq.top().second; } int L=pre[id],R=nxt[id];del[id]=1; ans=max(ans,pq.top().first); pq.pop(); if(abs((l[L].b-l[L].a)*(l[R].b-l[R].a))<eps)break; P p=cp(l[L],l[R]); l[L].b=l[R].a=p; nxt[L]=R;pre[R]=L; add(L);add(R); } printf("%.6lf",(double)ans); return 0; } |
Subscribe
计数器 9850846
OI 课件=>
OI 课件=>