首页 > 代码库 > [计算几何]离大海的最远点在哪里
[计算几何]离大海的最远点在哪里
题意:给定一个凸多边形,求一个点使得它到各条边的距离的最小值最大。
这本来是一道poj原题,n<=100,但是貌似精度有问题,poj死都过不去,以后再试试...
这次做的是一道改编题,n<=200000,一组数据。
显然可以二分答案,并且把边往里面推,但是这样的话常数太大过不了..
但是我们发现,一条边消失是在距离超过 它和相邻的边的角平分线的交点到它的距离 的时候。所以我们可以用一个堆来模拟推进,用双向链表维护相邻的边。
然后作为一个计算几何菜鸡,我做完感觉意识模糊...
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #define eps 1e-9 #define ld long double #define MAXN 200000 #define pa pair<ld,int> #define mp(x,y) make_pair(x,y) using namespace std; //******************** struct P{ ld x,y; P(ld _x=0,ld _y=0):x(_x),y(_y){} }s[MAXN+5]; struct L{P u,v;}l[MAXN+5]; P operator+(P x,P y){return P(x.x+y.x,x.y+y.y);} P operator-(P x,P y){return P(x.x-y.x,x.y-y.y);} ld operator*(P x,P y){return x.x*y.y-y.x*x.y;} P operator/(P x,ld y){return P(x.x/y,x.y/y);} P operator*(P x,ld y){return P(x.x*y,x.y*y);} ld dot(P x,P y){return x.x*y.x+x.y*y.y;} ld dis(P x){return sqrt(x.x*x.x+x.y*x.y);} P operator*(L a,L b){return a.u+a.v*(b.v*(a.u-b.u)/(a.v*b.v));} //******************** int n,ne[MAXN+5],la[MAXN+5]; priority_queue<pa > q; bool mark[MAXN+5]; L solve(L a,L b){return (L){a*b,a.v*dis(b.v)-b.v*dis(a.v)};} ld calc(int x) { P p=solve(l[la[x]],l[x])*solve(l[x],l[ne[x]]); //cout<<"calc"<<x<<" "<<-fabs(p*l[x].v/dis(l[x].v))<<endl; return -fabs((l[x].v*(p-l[x].u))/dis(l[x].v)); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%Lf%Lf",&s[i].x,&s[i].y); for(int i=1;i<=n;i++)ne[i-1]=i,la[i]=i-1; la[1]=n,ne[n]=1; for(int i=1;i<=n;i++)l[i]=(L){s[i],s[i]-s[la[i]]}; for(int i=1;i<=n;i++)q.push(mp(calc(i),i)); for(int i=2;i<n;i++) { while(!q.empty()&&mark[q.top().second])q.pop(); int x=q.top().second;mark[x]=1; la[ne[x]]=la[x];ne[la[x]]=ne[x]; q.push(mp(calc(la[x]),la[x])); q.push(mp(calc(ne[x]),ne[x])); } printf("%0.8Lf",-q.top().first); return 0; }
[计算几何]离大海的最远点在哪里
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。