注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3911]SGU383 Caravans(三角剖分)  

2015-03-01 18:33:42|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3911: SGU383 Caravans

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 9  Solved: 4
[Submit][Status][Discuss]

Description

在这个任务中,你的目标是掠夺商队。
在沙漠中有n个绿洲(对于我们而言,它们在平面上的点)。有时商队从一个绿洲到另一个绿洲。为了掠夺它们,你应该预测其路径。但如何做呢?Nomad给出了解决方案。商队的速度是恒定的,他们尽量减少在绿洲外的最长时间。所以,你可以得出结论,即最佳路径是折线。
给定绿洲的坐标和m对商队的线路,出发点为编号为si的绿洲,目的地为编号为ti的绿洲,将最佳路径的最大长度输出。保证所有绿洲位置不同。

Input

第一行一个正整数n为绿洲的数量
接下来n行,每行两个整数x,y表示绿洲在二维平面上的点坐标
接下来一行为一个正整数m为商队数量
接下来m行,每行两个正整数si,ti,为第i个商队的起点和终点

Output

输出m行,每行一个6位小数,为最佳路径上的最大长度

Sample Input

3 0 0 50 10 150 0 3 1 2 1 3 2 3

Sample Output

50.990195 100.498756 100.498756

HINT

n,m<=100000
0<=x,y<100000
三角剖分

Solution

三角剖分出最小生成树之后,就是跟noip2013货车运输一样的了,lca倍增询问。
三角剖分就是能在O(n)或者O(nlogn)的时间內将平面上的点集用许多互不相交的三角形连起来,这些三角形有一个共同的性质:过该三角形的外接圆内不含其他任何点,称为空圆。
分治法求解三角剖分:
1. 按x-y排序并去重
2. 递归做 work(l,mid),work(mid+1,r);
3. 合并(l,mid)~(mid+1,r)

递归边界条件为当前处理的点数<=3,此时直接两两连边
合并第一步为找到两块点集的下公切线,这一步直接用凸包求就可以了。
然后就是把相邻两个点集连在一起。
假设当前刚刚连的一条边左端点为第ld号点,右端点为第rd号点。
我们遍历所有与当前ld,rd相邻的点,这些点中必定存在一个点id使得以三点(ld,rd,id)构成的圆不包含当前其它任何点。于是直接扫一遍,如果新加的点id'在圆(ld,rd,id)内则id=id'
然后就是连接这个点id,如果id原来在左边就连边(id,rd),删掉之前端点为ld,与(id,rd)有交的边,然后更新ld=id。id在右边同理。
删边只要用双向链表删就可以了。
由于每一步操作,边数都是O(n)的,所以整个复杂度是O(nlogn)的。

Code

/**************************************************************
    Problem: 3911
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:12408 ms
    Memory:93416 kb
****************************************************************/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100010
#define sqr(x) ((x)*(x))
#define max(a,b) (a>b?a:b)
int aa;char ch;int F(){
while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
typedef double ld;
struct P{ld x,y;}p[N];// | -> dot & -> cross
#define PP const P&
bool operator<(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
P operator+(PP a,PP b){return (P){a.x+b.x,a.y+b.y};}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
P operator*(PP a,ld b){return (P){a.x*b,a.y*b};}
P operator/(PP a,ld b){return (P){a.x/b,a.y/b};}
P operator*(PP a,PP b){ld d=a.x*b.x,e=a.y*b.y,f=(a.x+a.y)*(b.x+b.y);return (P){d-e,f-e-d};}
ld operator|(PP a,PP b){return a.x*b.x+a.y*b.y;}
ld operator&(PP a,PP b){return a.x*b.y-a.y*b.x;}
ld dis2(PP a){return sqr(a.x)+sqr(a.y);}
int dcmp(ld x){return x>0?1:x<0?-1:0;}
char cross(PP a,PP b,PP c,PP d){
return dcmp((c-a)&(d-a))*dcmp((c-b)&(d-b))==-1&&dcmp((a-c)&(b-c))*dcmp((a-d)&(b-d))==-1;
}
ld check(PP a,PP b,PP c){return (b-a)&(c-a);}

struct P3{ld x,y,z;}ori[N];
#define PP3 const P3&
#define rd(a) (P3){a.x,a.y,sqr(a.x)+sqr(a.y)}
bool operator<(PP3 a,PP3 b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
P3 operator-(PP3 a,PP3 b){return (P3){a.x-b.x,a.y-b.y,a.z-b.z};}
ld operator|(PP3 a,PP3 b){return a.x*b.x+a.y*b.y+a.z*b.z;}
P3 operator&(PP3 a,PP3 b){return (P3){a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x};}
char incir(PP a,PP b,PP c,PP d){
P3 aa=rd(a),bb=rd(b),cc=rd(c),dd=rd(d);
if(check(a,b,c)<0)std::swap(bb,cc);
return ((dd-aa)|((bb-aa)&(cc-aa)))<0;
}

int n,m,i,j,et=1,la[N],ts,xx,yy,fa[N][20],tot,cnt,dep[N],l,r,q[N<<2],ufs[N];ld mx[N][20];
struct E{int to,l,r;}e[N<<5];
void add(int x,int y){
e[++et]=(E){y,la[x],0},e[e[et].l].r=la[x]=et;
e[++et]=(E){x,la[y],0},e[e[et].l].r=la[y]=et;
}
void del(int x){e[e[x].r].l=e[x].l,e[e[x].l].r=e[x].r,la[e[x^1].to]==x?la[e[x^1].to]=e[x].l:1;}
void delaunay(int l,int r){
int i,j,mid=l+r>>1,ld=0,rd,op,id;
if(r-l<=2){
for(i=l;i<=r;i++)
for(j=i+1;j<=r;j++)add(i,j);
return;
}
delaunay(l,mid),delaunay(mid+1,r);

for(ts=0,i=l;i<=r;q[++ts]=i++)//tubao
while(ts>1&&check(p[q[ts-1]],p[q[ts]],p[i])<0)ts--;
for(i=1;i<ts&&!ld;i++)if(q[i]<=mid&&q[i+1]>mid)ld=q[i],rd=q[i+1];

for(add(ld,rd);;){
id=op=0;
for(i=la[ld];i;i=e[i].l)
if(check(p[ld],p[rd],p[e[i].to])>0&&(!id||incir(p[ld],p[rd],p[id],p[e[i].to])))id=e[i].to,op=-1;
for(i=la[rd];i;i=e[i].l)
if(check(p[rd],p[ld],p[e[i].to])<0&&(!id||incir(p[ld],p[rd],p[id],p[e[i].to])))id=e[i].to,op=1;
if(!id)break;
if(op==-1){
for(i=la[ld];i;i=e[i].l)
if(cross(p[rd],p[id],p[ld],p[e[i].to]))del(i),del(i^1),i=e[i].r;
ld=id;
}else{
for(i=la[rd];i;i=e[i].l)
if(cross(p[ld],p[id],p[rd],p[e[i].to]))del(i),del(i^1),i=e[i].r;
rd=id;
}
add(ld,rd);
}
}
struct D{int x,y;ld v;}d[N<<3];
bool operator<(const D&i,const D&j){return i.v<j.v;}
int gf(int x){return ufs[x]==x?x:ufs[x]=gf(ufs[x]);}
struct G{int to;double v;int nxt;}g[N<<3];
#define addg(x,y,v) (g[++et]=(G){y,v,la[x]},la[x]=et)
ld query(){
int x,y,k,i;ld ans=0;x=F(),y=F();
if(dep[x]<dep[y])k=x,x=y,y=k;
for(k=dep[x]-dep[y],i=0;k;k>>=1,i++)if(k&1)
ans=max(ans,mx[x][i]),x=fa[x][i];
if(x==y)return ans;

for(i=0;fa[x][i]!=fa[y][i];i++);
for(i--;~i;i--)if(fa[x][i]!=fa[y][i])
ans=max(ans,max(mx[x][i],mx[y][i])),x=fa[x][i],y=fa[y][i];
ans=max(ans,max(mx[x][0],mx[y][0]));return ans;
}
int main(){
for(n=F(),i=1;i<=n;i++)xx=F(),yy=F(),p[i]=(P){xx,yy},ori[i]=(P3){xx,yy,i},ufs[i]=i;
std::sort(p+1,p+1+n);std::sort(ori+1,ori+1+n);delaunay(1,n);

for(i=1;i<=n;i++)
for(j=la[i];j;j=e[j].l)xx=ori[i].z,yy=ori[e[j].to].z,
d[++tot]=(D){xx,yy,dis2(p[i]-p[e[j].to])};
std::sort(d+1,d+1+tot);

memset(la,0,sizeof(la)),et=0;
for(i=1;i<=tot&&cnt<n-1;i++)if(gf(d[i].x)!=gf(d[i].y))
cnt++,ufs[ufs[d[i].x]]=ufs[d[i].y],
addg(d[i].x,d[i].y,d[i].v),addg(d[i].y,d[i].x,d[i].v);

for(q[l=r=1]=dep[1]=1;l<=r;l++)
for(i=la[q[l]];i;i=g[i].nxt)if(!dep[g[i].to])
for(dep[q[++r]=g[i].to]=dep[q[l]]+1,fa[g[i].to][j=0]=q[l],mx[g[i].to][0]=g[i].v;fa[g[i].to][j];j++)
fa[g[i].to][j+1]=fa[fa[g[i].to][j]][j],mx[g[i].to][j+1]=max(mx[g[i].to][j],mx[fa[g[i].to][j]][j]);

for(m=F();m--;printf("%.6lf\n",sqrt()));
}


一个Linux下可视化小程序

  评论这张
 
阅读(524)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018