记录编号	117049	评测结果	AAAAAAAAAA
题目名称	[AHOI2005] 穿越磁场	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2014-08-27 22:21:23	内存使用	97.07 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
#include<map>
using namespace std;
const int SIZEN=10050,SIZECO=250,INF=0x7fffffff/2;
int N,MX=0;
bool c[SIZEN][SIZEN]={0};
map<int,int> X,Y;
int id[SIZECO][SIZECO]={0};
class POINT{
public:
	int x,y;
	void reassign(void){x=X[x],y=Y[y];}
};
POINT start,end;
POINT rect[SIZEN][2];
void assign(map<int,int> &s){
	int tot=0;
	for(map<int,int>::iterator key=s.begin();key!=s.end();key++)
		key->second=++tot;
	MX=max(MX,tot+1);
}
void discretize(void){
	assign(X),assign(Y);
	for(int i=1;i<=N;i++) rect[i][0].reassign(),rect[i][1].reassign();
	start.reassign(),end.reassign();
}
bool in_rect(int x,int y,int k){
	return x>=rect[k][0].x&&x<rect[k][1].x&&y>=rect[k][0].y&&y<rect[k][1].y;
}
bool test_cross(int x1,int y1,int x2,int y2){
	for(int i=1;i<=N;i++){
		if(in_rect(x1,y1,i)^in_rect(x2,y2,i)) return true;
	}
	return false;
}
bool valid(int x,int y){
	return 0<=x&&x<=MX&&0<=y&&y<=MX;
}
int nowcol;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void DFS_color(int x,int y){
	id[x][y]=nowcol;
	for(int d=0;d<4;d++){
		int nx=x+dx[d],ny=y+dy[d];
		if(!valid(nx,ny)||id[nx][ny]) continue;
		if(!test_cross(x,y,nx,ny)) DFS_color(nx,ny);
	}
}
void floodfill(void){
	nowcol=0;
	for(int x=0;x<=MX;x++)
		for(int y=0;y<=MX;y++)
			if(!id[x][y]) nowcol++,DFS_color(x,y);
}
int S,T;
void makegraph(void){
	for(int x=0;x<=MX;x++)
		for(int y=0;y<=MX;y++){
			if(x==start.x&&y==start.y) S=id[x][y];
			if(x==end.x&&y==end.y) T=id[x][y];
			for(int d=0;d<4;d++){
				int nx=x+dx[d],ny=y+dy[d];
				if(!valid(nx,ny)) continue;
				c[id[x][y]][id[nx][ny]]=c[id[nx][ny]][id[x][y]]=true;
			}
		}
}
int f[SIZEN]={0};
void get_dist(void){
	for(int i=1;i<SIZEN;i++) f[i]=INF;
	queue<int> Q;
	f[S]=0;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=1;i<=nowcol;i++){
			if(!c[x][i]) continue;
			if(f[x]+1<f[i]){
				f[i]=f[x]+1;
				Q.push(i);
			}
		}
	}
}
void read(void){
	scanf("%d",&N);
	int x,y,c;
	for(int i=1;i<=N;i++){
		scanf("%d%d%d",&x,&y,&c);
		X[x]=0,Y[y]=0,X[x+c]=0,Y[y+c]=0;
		rect[i][0]=(POINT){x,y},rect[i][1]=(POINT){x+c,y+c};
	}
	scanf("%d%d",&start.x,&start.y);
	X[start.x]=0,Y[start.y]=0;
	scanf("%d%d",&end.x,&end.y);
	X[end.x]=0,Y[end.y]=0;
}
int main(){
	freopen("cross.in","r",stdin);
	freopen("cross.out","w",stdout);
	read();
	discretize();
	floodfill();
	makegraph();
	get_dist();
	printf("%d\n",f[T]);
	return 0;
}