跑得比谁都快(fast.cpp/c/pas)

福州一中 翁家翌

时间限制：1000MS 内存限制：233MB

【Description】

n+e又即将踏上拯救妹子的道路……

这次的拯救目标是——爱和正义的小叶妹子。

n+e来到boss的洞穴门口，他一下子就懵了，因为面前不只是一只boss，而是上万只boss。当n+e意识到自己还是等级1的时候，他明白这就是一个不可能完成的任务。

但他不死心，他可是跑得比谁都快，他在想，能不能避开boss去拯救妹子呢？

Boss的洞穴可以看成一个矩形，n+e在左下角（0,0），妹子在右上角（A,B）。n+e为了避开boss，当然是离boss距离越远越好了，所以n+e决定找一条路径使到距离boss的最短距离最远。

Ps:n+e走的方向是任意的。

你可以帮帮他吗？

当n+e找到了美丽漂亮的小叶妹子，立刻就被boss包围了！！！n+e缓闭双眼，举手轻挥，白光一闪后使用了回城卷轴，回到了城堡，但只有小叶妹子回去了……因为n+e忘了进入回城的法阵了。（然而并没有什么关系，他可是跑得比谁都快呢）

【Input Format】

第一行，输入三个数N,A,B，N表示boss的数目，A，B表示矩形的大小；

接下来n行，每行两个数表示boss的位置坐标(x,y)，保证0<=x<=A,0<=y<=B，并且坐标两两不同。

【Output Format】

输出一个小数，表示n+e的路径离boss的最远距离，精确到小数点后六位。

【Sample Input】

#1

2 10 10

5 4

2 1

#2

2 10.000000 10.000000

2.500000 7.500000

7.500000 2.500000

【Sample Output】

#1

2.000000

#2

3.535534

【Hint】

对于编号为奇数的点，输入数据中所有的数均为非负整数。

对于编号为偶数的点，输入数据中除N以外的数均保留6位小数。

PS：由于n+e跑得比谁都快，所以他决定卡你们的常数.....

（n+e：题面才不是我改的呢哼 是那个 伟(dong)大(xian)的(sheng)人 改的）

Sol

首先这题可以看成如下的模型： 随着时间的推移，在t时刻的点(x,y)会形成以(x,y)为圆心，t为半径的圆，问当(0,0)与(A,B)在平面上连通时的最大的t值。

算法1

对于n=2的点，无非就几种情况：圆碰到了边界，圆与圆碰在了一起。分类讨论一下。

期望得分：10

算法2

对于B=1，并且输入数据均为整数的情况，答案无非只有三种可能：1、0.5、sqrt(0.5)，判断一下就好了

期望得分：10

算法3

对于n比较小(<=100)的数据，可以先二分一个答案t，然后将n个点变成n个半径为t的圆，然后看一下(0,0)与(A,B)是否连通

左下角和右上角连通等价于对偶图中左上两条边和右下两条边不连通

因此将所有相交的圆之间连边，从左上两条边广搜即可

期望得分：30~40

（我会说网络上大部分都是这种犯逗的题解嘛= =）

算法4

考虑算法3的实质，就是将点对距离小于t的连边，然后看看有没有通路。

不妨将点对距离排序处理出来，这样问题就变成了从左下到右上找一条路最小值最大。

可以用Prim解决。

期望得分：70

算法5

平面欧几里德最小生成树问题是一个经典问题，能够用三角剖分在O(nlogn)的时间内解决

期望得分：100

心得体会：

一道看似无从下手的问题，通过一步步分析从而解决

平面几何的模型转换

对偶思想的运用

乱搞的运用

V图的运用

能够锻炼自己的代码能力

是一道大模板题一道大模板题大模板题大模板模板

Another Solution (->my ppt)

Code

#include<cstdio>
#include<cmath>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define sqr(x) ((x)*(x))
double x[100010],y[100010],d[100010],ans,A,B,tmp;
bool b[100010];int n,las;
int main(){
	freopen("fast.in","r",stdin);
	freopen("fast.out","w",stdout);
	scanf("%d%lf%lf",&n,&A,&B);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
	for(int i=1;i<=n;i++)d[i]=min(B-y[i],x[i]);
	d[n+1]=1e18;
	for(int j=1;j<=n;j++){
		tmp=1e18;
		for(int i=1;i<=n+1;i++)if(d[i]<=tmp&&!b[i])tmp=d[i],las=i;
		if(b[las]=1,b[n+1])break;
		for(int i=1;i<=n;i++)  
		if(!b[i])d[i]=min(d[i],max(d[las],sqrt(sqr(x[las]-x[i])+sqr(y[las]-y[i]))*.5));
		d[n+1]=min(d[n+1],max(d[las],min(y[las],A-x[las])));    
	}
	printf("%lf\n",d[n+1]);
}

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100010
typedef double ld;
int n,fa[N],tot;ld A,B;
struct P{ld x,y;}a[N],rtt;
bool operator<(const P&a,const P&b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
P operator-(const P&a,const P&b){return (P){a.x-b.x,a.y-b.y};}
P operator*(const P&a,const P&b){return (P){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
ld len(const P&a){return a.x*a.x+a.y*a.y;}
struct E{int x,y;ld v;}e[N*40];
bool operator<(const E&a,const E&b){return a.v<b.v;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
#define min(a,b) (a<b?a:b)
#define sqr(a) ((a)*(a))
int main(){
	freopen("fast.in","r",stdin);
	freopen("fast.out","w",stdout);
	scanf("%d%lf%lf",&n,&A,&B);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y),fa[i]=i;fa[n+1]=n+1;
	std::sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=38&&i+j<=n;j++)e[++tot]=(E){i,i+j,len(a[i]-a[i+j])};
	for(int i=1;i<=n;i++)e[++tot]=(E){0,i,sqr(min(a[i].x,B-a[i].y)*2)},e[++tot]=(E){n+1,i,sqr(min(A-a[i].x,a[i].y)*2)};
	std::sort(e+1,e+1+tot);
	for(int i=1;i<=tot;i++)
	if(gf(e[i].x)!=gf(e[i].y)){
		fa[fa[e[i].x]]=fa[e[i].y];
		if(gf(0)==gf(n+1))return printf("%lf\n",sqrt(e[i].v)*0.5),0;
	}
}

#include<cstdio>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<algorithm>
#define N 100010
using namespace std;
typedef double ld;
int n,tot;ld A,B;
struct P{ld x,y;int ind;}a[N],rtt;
bool operator<(const P&a,const P&b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
P operator-(const P&a,const P&b){return (P){a.x-b.x,a.y-b.y,a.ind};}
P operator*(const P&a,const P&b){return (P){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x,a.ind};}
ld len(const P&a){return a.x*a.x+a.y*a.y;}
#define sqr(a) ((a)*(a))
std::priority_queue<pair<double,int> > Q;
bool Vis[N];
double Dis[N],D[N],tmpD[N],tmp2[N];
int main(){
	int Seed = 1626;
	srand(Seed);
	freopen("fast.in","r",stdin);
	freopen("fast.out","w",stdout);
	scanf("%d%lf%lf",&n,&A,&B);rtt=(P){cos(acos(-1)/3),sin(acos(-1)/3)};
	for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y),a[i].ind=i;
	for(int i=1;i<=n;i++){
		tmpD[i]=sqr(min(a[i].x,B-a[i].y))*4,
		tmp2[i]=sqr(min(A-a[i].x,a[i].y))*4;
	}
	std::sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		D[i]=tmpD[a[i].ind];
		Dis[i]=tmp2[a[i].ind];
		Q.push(make_pair(-D[i],i));
	}
	D[n+1]=1e20;
	double Ans=0;
	while(!Q.empty()){
		pair<double,int> X;
		X=Q.top();Q.pop();
		if(Vis[X.second])continue;
		Ans=std::max(-X.first,Ans);
		Vis[X.second]=1;
		if(Vis[n+1]) break;
		int P=rand()%20+80;
		for(int i=max(1,X.second-P);i<=min(X.second+P,n);i++)
			if(D[i]>len(a[X.second]-a[i])){
				D[i]=len(a[X.second]-a[i]);
				Q.push(make_pair(-D[i],i));
			}
		if(D[n+1]>Dis[X.second]){
			D[n+1]=Dis[X.second];
			Q.push(make_pair(-D[n+1],n+1));
		}
	}
	printf("%lf\n",sqrt(Ans)*0.5);
}

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100010
typedef double ld;
struct P{
	ld x,y;
#define PP const P&
	bool operator<(PP a)const {return x<a.x||x==a.x&&y<a.y;}
	P operator-(PP a)const {return (P){x-a.x,y-a.y};}
	ld operator&(PP a)const {return x*a.y-y*a.x;}
	ld operator|(PP a)const {return x*a.x+y*a.y;}
}p[N],bo;
#define check(a,b,c) ((b-a)&(c-a))
ld dis(PP a){return a.x*a.x+a.y*a.y;}
#define cross(a,b,c,d) (check(p[a],p[c],p[d])*check(p[b],p[c],p[d])<0&&check(p[c],p[a],p[b])*check(p[d],p[a],p[b])<0)
struct P3{
	ld x,y,z;
	P3 operator-(const P3&a)const {return (P3){x-a.x,y-a.y,z-a.z};}
	ld operator|(const P3&a)const {return x*a.x+y*a.y+z*a.z;}
	P3 operator&(const P3&a)const {return (P3){y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x};}
};
#define gp3(a) (P3){a.x,a.y,a.x*a.x+a.y*a.y}
bool incir(int a,int b,int c,int d){
	P3 aa=gp3(p[a]),bb=gp3(p[b]),cc=gp3(p[c]),dd=gp3(p[d]);
	if(check(p[a],p[b],p[c])<0)std::swap(bb,cc);
	return (check(aa,bb,cc)|(dd-aa))<0;
}
int n,la[N],et=1,fa[N],q[N],tot,i,j;
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
struct E{int to,l,r;}e[N*10];
void add(int x,int y){
	e[++et]=(E){y,la[x]},e[la[x]].r=et,la[x]=et;
	e[++et]=(E){x,la[y]},e[la[y]].r=et,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){
	if(r-l<=2){
		for(int i=l;i<r;i++)
		for(int j=i+1;j<=r;j++)add(i,j);
		return;
	}
	int i,j,mid=l+r>>1,ld=0,rd=0,id,op;
	delaunay(l,mid),delaunay(mid+1,r);
	for(tot=0,i=l;i<=r;q[++tot]=i++)
	while(tot>1&&check(p[q[tot-1]],p[q[tot]],p[i])<0)tot--;
	for(i=1;i<tot&&!ld;i++)if(q[i]<=mid&&mid<q[i+1])ld=q[i],rd=q[i+1];
	for(;add(ld,rd),1;){
		id=op=0;
		for(i=la[ld];i;i=e[i].l)if(check(p[ld],p[rd],p[e[i].to])>0)
		if(!id||incir(ld,rd,id,e[i].to))op=-1,id=e[i].to;
		for(i=la[rd];i;i=e[i].l)if(check(p[rd],p[ld],p[e[i].to])<0)
		if(!id||incir(ld,rd,id,e[i].to))op=1,id=e[i].to;
		if(op==0)break;
		if(op==-1){
			for(i=la[ld];i;i=e[i].l)
			if(cross(rd,id,ld,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(ld,id,rd,e[i].to))del(i),del(i^1),i=e[i].r;
			rd=id;
		}
	}
}
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int bb;ld aa,ee;ld F(){
	while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
	while(ch=getc(),isd(ch))aa=aa*10+ch-'0';ee=1;
	if(ch=='.')while(ch=getc(),isd(ch))aa+=(ch-'0')*(ee*=0.1);return bb?aa:-aa;
}
struct D{int x,y;ld v;}d[N<<3];
bool operator<(const D&i,const D&j){return i.v<j.v;}
#define min(a,b) (a<b?a:b)
#define sqr(x) ((x)*(x))
int main(){
	freopen("fast.in","r",stdin);
	freopen("fast.out","w",stdout);
	for(scanf("%d",&n),bo=(P){F(),F()},i=1;i<=n;i++)p[i]=(P){F(),F()},fa[i]=i;fa[n+1]=n+1;
	std::sort(p+1,p+1+n);delaunay(1,n);
	for(tot=0,i=1;i<=n;i++)
	for(j=la[i];j;j=e[j].l)if(i>e[j].to)
	d[++tot]=(D){i,e[j].to,dis(p[i]-p[e[j].to])};
	for(i=1;i<=n;i++)d[++tot]=(D){0,i,sqr(2*min(p[i].x,bo.y-p[i].y))},d[++tot]=(D){i,n+1,sqr(2*min(bo.x-p[i].x,p[i].y))};
	std::sort(d+1,d+1+tot);
	for(i=1;i<=tot;i++)if(gf(d[i].x)!=gf(d[i].y)){
		fa[fa[d[i].x]]=fa[d[i].y];
		if(gf(0)==gf(n+1))return printf("%lf\n",sqrt(d[i].v)*0.5),0;
	}
}