BZOJ:4219: 跑得比谁都快 3007: 拯救小云公主

4219: 跑得比谁都快

3007: 拯救小云公主

三角剖分的解释可以看这里:http://www.cnblogs.com/Enceladus/p/6706444.html

后一道是前一道的弱化版。

如果考虑一下二分答案再判定,判定的过程无非就是把每个点变成一个以答案为半价的圆,然后如果左上和右下被切开了肯定就不合法,那就变成1001里面那种对偶图,跑一下spfa就好。

再看其实就不需要二分答案了,把各个boss连接起来,二分的答案达到边权一半时这两个圆就相交。整条路径会在达到最大边权的时候完全连通,那么最大边权最小的路径就是答案。

看了题解才意识到这一点,我的破题能力是不是吃枣药丸啊?

所以就三角剖分+最小生成树,至于三角剖分我选择拉模版。

貌似得用long double

#include<cmath>
#include<cstdio>
#include<algorithm>
#define eps 1e-12
#define MN 110001
#define ld long double
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
struct po{ld x,y;};
struct na{po p;int n;}p[MN];
struct e{int x,y,ne,pre;}b[MN<<];
struct bi{int x,y;ld z;}B[MN<<];
bool operator < (bi a,bi b){return a.z<b.z;}
bool operator < (na a,na b){return a.p.x==b.p.x?a.p.y<b.p.y:a.p.x<b.p.x;}
int n,m,num=,l[MN],st[MN],top,NUM=,x,y,_l[MN],_num=,fa[MN];ld _A,_B;
inline void _add(int x,int y){b[++num].x=x;b[num].y=y;b[num].ne=l[x];b[l[x]].pre=num;l[x]=num;}
inline void add(int x,int y){_add(x,y);_add(y,x);}
inline void _del(int i){if(l[b[i].x]==i)l[b[i].x]=b[i].ne;else{b[b[i].pre].ne=b[i].ne;if(b[i].ne)b[b[i].ne].pre=b[i].pre;}}
inline void del(int i){_del(i);_del(i^);}
ld cha(po a,po b,po c){return (b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y);}
bool _cha(po a,po b,po c){return cha(a,b,c)<=;}
inline bool ju(po a,po b,po c,po d){return (_cha(a,b,c)^_cha(a,b,d))&&(_cha(c,d,a)^_cha(c,d,b));}
ld sqr(ld x){return x*x;}
inline ld min(ld a,ld b){return a<b?a:b;}
bool incir(po a,po b,po c,po d){
ld m=(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y))*.;
ld x=(sqr(a.x)*(b.y-c.y)+sqr(b.x)*(c.y-a.y)+sqr(c.x)*(a.y-b.y)-(a.y-b.y)*(b.y-c.y)*(c.y-a.y))/m;
ld y=((a.x-b.x)*(b.x-c.x)*(c.x-a.x)-sqr(a.y)*(b.x-c.x)-sqr(b.y)*(c.x-a.x)-sqr(c.y)*(a.x-b.x))/m;
return sqrt(sqr(x-a.x)+sqr(y-a.y))+eps>sqrt(sqr(x-d.x)+sqr(y-d.y));
}
void work(int L,int R){
if (R-L<=){
for (int i=L;i<R;i++)
for (int j=i+;j<=R;j++) add(i,j);
return;
}
int mid=L+R>>;
work(L,mid);work(mid+,R);
top=;
for (int i=L;i<=R;st[++top]=i++)
while (top>&&cha(p[st[top-]].p,p[st[top]].p,p[i].p)<) top--;
int Ld,Rd,id;
for (int i=;i<top;i++)
if (st[i]<=mid&&st[i+]>mid) Ld=st[i],Rd=st[i+];
add(Ld,Rd);
for(;;){
id=-;
for (int i=l[Ld];i;i=b[i].ne)
if (b[i].y!=Rd)
if (cha(p[b[i].y].p,p[Ld].p,p[Rd].p)>&&(id==-||incir(p[Ld].p,p[Rd].p,p[id].p,p[b[i].y].p))) id=b[i].y;
for (int i=l[Rd];i;i=b[i].ne)
if (b[i].y!=Ld)
if (cha(p[Ld].p,p[Rd].p,p[b[i].y].p)>&&(id==-||incir(p[Ld].p,p[Rd].p,p[id].p,p[b[i].y].p))) id=b[i].y;
if (id==-) break; if (id<=mid){
for (int i=l[Ld];i;i=b[i].ne)
if (b[i].y!=Rd)
if (ju(p[id].p,p[Rd].p,p[b[i].y].p,p[Ld].p)) del(i);
Ld=id;
}else{
for (int i=l[Rd];i;i=b[i].ne)
if (b[i].y!=Ld)
if (ju(p[id].p,p[Ld].p,p[b[i].y].p,p[Rd].p)) del(i);
Rd=id;
}
add(Ld,Rd);
}
}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
register int i,j;
n=read();scanf("%Lf%Lf",&_A,&_B);
for (i=;i<n;i++) scanf("%Lf%Lf",&p[i].p.x,&p[i].p.y),p[i].n=i+,fa[i]=i;
sort(p,p+n);
work(,n-);
for (i=;i<n;i++)
for (j=l[i];j;j=b[j].ne) if (b[j].y>i) B[NUM].x=i,B[NUM].y=b[j].y,B[NUM++].z=sqrt(sqr(p[i].p.x-p[b[j].y].p.x)+sqr(p[i].p.y-p[b[j].y].p.y))/;
for (i=;i<n;i++) B[NUM].x=i,B[NUM].y=n,B[NUM++].z=min(p[i].p.x,_B-p[i].p.y);
for (i=;i<n;i++) B[NUM].x=i,B[NUM].y=n+,B[NUM++].z=min(_A-p[i].p.x,p[i].p.y);
n+=;fa[n-]=n-;fa[n-]=n-;
sort(B,B+NUM);
for (i=;i<NUM;i++){
int x=gf(B[i].x),y=gf(B[i].y);
if (x==y) continue;
fa[x]=y;
if (gf(n-)==gf(n-)) return printf("%.6Lf\n",B[i].z),;
}
}

upd 2017/12/26

  代码被hack了T_T,详见http://www.cnblogs.com/Enceladus/p/6706444.html

上一篇:遍历输出tuple元素的简洁方式(C++11)


下一篇:Some Skills in Visual Studio