记录编号	125961	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[BOI2007]修建栅栏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.708 s
提交时间	2014-10-10 19:41:51	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const double eps=1e-8;
const int SIZEN=810,INF=0x7fffffff/2;
class RECT{
public:
	double x1,x2,y1,y2;//x1<=x2,y1<=y2
};
bool inter(RECT a,RECT b){//是否严格相交
	if(b.x2<=a.x1||b.x1>=a.x2) return false;
	if(b.y2<=a.y1||b.y1>=a.y2) return false;
	return true;
}
int M;
RECT R[SIZEN];
double Ox,Oy;//射线从这个点出发,向右
bool cross(double x,double y1,double y2){//是否被射线穿过
	if(y1>y2) swap(y1,y2);
	if(x<=Ox) return false;
	return y1<Oy&&y2>Oy;
}
class POINT{
public:
	double x,y;
};
void print(POINT p){
	cout<<"("<<p.x<<" "<<p.y<<")";
}
double M_dist(POINT a,POINT b){
	return fabs(a.x-b.x)+fabs(a.y-b.y);
}
bool lineinter(POINT a,POINT b){//是否穿过了某矩形
	double x1=a.x,x2=b.x,y1=a.y,y2=b.y;
	if(x1>x2) swap(x1,x2);
	if(y1>y2) swap(y1,y2);
	for(int i=1;i<=M;i++)
		if(inter((RECT){x1,x2,y1,y2},R[i])) return true;
	return false;
}
POINT P[SIZEN];
int Ptot=0;
int N;
vector<pair<int,int> > c[SIZEN];
void addedge(int a,int b,int w){
	c[a].push_back(make_pair(b,w));
	c[b].push_back(make_pair(a,w));
}
void testedge(int i,int j){//P[i]和P[j]
	int d=M_dist(P[i],P[j]);
	if(d<eps) return;
	POINT M;
	M=(POINT){P[i].x,P[j].y};
	if(!lineinter(P[i],M)&&!lineinter(M,P[j])){
		if(cross(P[i].x,P[i].y,M.y)){
			addedge(i,j+Ptot,d);
			addedge(i+Ptot,j,d);
		}
		else{
			addedge(i,j,d);
			addedge(i+Ptot,j+Ptot,d);
		}
	}
	M=(POINT){P[j].x,P[i].y};
	if(!lineinter(P[i],M)&&!lineinter(M,P[j])){
		if(cross(P[j].x,M.y,P[j].y)){
			addedge(i,j+Ptot,d);
			addedge(i+Ptot,j,d);
		}
		else{
			addedge(i,j,d);
			addedge(i+Ptot,j+Ptot,d);
		}
	}
}
void makegraph(void){
	N=2*Ptot;
	for(int i=1;i<=Ptot;i++)
		for(int j=i+1;j<Ptot;j++) testedge(i,j);
}
int f[SIZEN];
bool inq[SIZEN];
queue<int> Q;
int SPFA(int S,int T){
	for(int i=1;i<=N;i++) f[i]=INF;
	memset(inq,0,sizeof(inq));
	Q.push(S);f[S]=0;inq[S]=true;
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i].first;
			if(f[x]+c[x][i].second<f[u]){
				f[u]=f[x]+c[x][i].second;
				if(!inq[u]){
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
	return f[T];
}
void work(void){
	int ans=INF;
	for(int i=1;i<=Ptot;i++) ans=min(ans,SPFA(i,i+Ptot));
	printf("%d\n",ans);
}
void read(void){
	scanf("%d",&M);
	for(int i=1;i<=M;i++){
		scanf("%lf%lf%lf%lf",&R[i].x1,&R[i].y1,&R[i].x2,&R[i].y2);
		P[++Ptot]=(POINT){R[i].x1,R[i].y1};
		P[++Ptot]=(POINT){R[i].x1,R[i].y2};
		P[++Ptot]=(POINT){R[i].x2,R[i].y1};
		P[++Ptot]=(POINT){R[i].x2,R[i].y2};
	}
	Ox=R[1].x1+0.5,Oy=R[1].y1+0.5;
}
int main(){
	freopen("boi2007_fence.in","r",stdin);
	freopen("boi2007_fence.out","w",stdout);
	read();
	makegraph();
	work();
	return 0;
}