Beyond the Void

/* 
 * Problem: AHOI2005 cross
 * Author: Guo Jiabao
 * Time: 2009.4.17 10:32
 * State: Solved
 * Memo: 离散化 + 染色 + BFS
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXL=405,INF=0x7FFFFFF,MAXC=MAXN*MAXN;
const int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
using namespace std;
struct Queue
{
	int Q[MAXC],head,tail,size;
	Queue() {head=size=0;tail=-1;}
	void ins(int p)
	{
		if (++tail>=MAXC) tail=0;
		Q[tail]=p;
		size++;
	}
	int pop()
	{
		int r=Q[head];
		if (++head>=MAXC) head=0;
		size--;
		return r;
	}
}Q;
struct edge
{
	edge *next;
	int t;
}*V[MAXC];
struct point
{
	int x,y;
}S,T,Rect[MAXN][2],*P[MAXN*2+3],MaxP;
int N,CP,Color,Start,Target,Ans;
int TK[MAXN*2+3];
int Bel[MAXL][MAXL];
int Dist[MAXC];
void init()
{
	int i,x,y,c;
	freopen("cross.in","r",stdin);
	freopen("cross.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		Rect[i][0].x=x;Rect[i][0].y=y;
		Rect[i][1].x=x+c;Rect[i][1].y=y+c;
		P[++CP]=&Rect[i][0]; P[++CP]=&Rect[i][1];
	}
	scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);
	P[++CP]=&S; P[++CP]=&T;
}
inline int cmpx(const void *a,const void *b)
{
	point *A=*(point **)a, *B=*(point **)b;
	return A->x - B->x;
}
inline int cmpy(const void *a,const void *b)
{
	point *A=*(point **)a, *B=*(point **)b;
	return A->y - B->y;
}
void dispose()
{
	int i;point PT={-100000,-100000};
	MaxP.x=MaxP.y=0;
	P[0]=&PT;TK[0]=0;
	qsort(P+1,CP,sizeof(P[0]),cmpx);
	for (i=1;i<=CP;i++)
	{
		TK[i]=TK[i-1];
		if (P[i]->x!=P[i-1]->x)
			TK[i]++;
		if (TK[i] > MaxP.x)
			MaxP.x=TK[i];
	}
	for (i=1;i<=CP;i++)
		P[i]->x=TK[i];
	qsort(P+1,CP,sizeof(P[0]),cmpy);
	for (i=1;i<=CP;i++)
	{
		TK[i]=TK[i-1];
		if (P[i]->y!=P[i-1]->y)
			TK[i]++;
		if (TK[i] > MaxP.y)
			MaxP.y=TK[i];
	}
	for (i=1;i<=CP;i++)
		P[i]->y=TK[i];
}
inline bool inrange(int x,int y)
{
	return x>=0 && y>=0 && x<=MaxP.x+1 && y<=MaxP.y+1;
}
inline bool inrect(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 cross(int x1,int y1,int x2,int y2)
{
	int i;
	for (i=1;i<=N;i++)
	{
		if (inrect(x1,y1,i) ^ inrect(x2,y2,i))
			return true;
	}
	return false;
}
void dfscolor(int x,int y)
{
	int k,tx,ty;
	Bel[x][y]=Color;
	for (k=0;k<4;k++)
	{
		tx=x+dx[k]; ty=y+dy[k];
		if (inrange(tx,ty) && !Bel[tx][ty] && !cross(x,y,tx,ty))
		{
			dfscolor(tx,ty);
		}
	}
}
void floodfill()
{
	int x,y;
	for (x=1;x<MaxP.x;x++)
	{
		for (y=1;y<MaxP.y;y++)
		{
			if (!Bel[x][y])
			{
				Color++;
				dfscolor(x,y);
			}
		}
	}
}
inline void addedge(int a,int b)
{
	edge e={V[a],b};
	V[a]=new edge(e);
}
void MakeGraph()
{
	int x,y,tx,ty,k,a,b;
	for (x=1;x<=MaxP.x;x++)
	{
		for (y=1;y<=MaxP.y;y++)
		{
			a=Bel[x][y];
			if (x==S.x && y==S.y)
				Start=a;
			if (x==T.x && y==T.y)
				Target=a;
			for (k=0;k<4;k++)
			{
				tx=x+dx[k]; ty=y+dy[k];
				if (inrange(tx,ty))
				{
					b=Bel[tx][ty];
					addedge(a,b);
				}
			}
		}
	}
}
void BFS()
{
	int i,j;
	memset(Dist,-1,sizeof(Dist));
	Q.ins(Start);
	Dist[Start]=0;
	while (Q.size)
	{
		i=Q.pop();
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (Dist[j]==-1)
			{
				Dist[j]=Dist[i]+1;
				if (j==Target)
					return;
				Q.ins(j);
			}
		}
	}
}
void solve()
{
	dispose();
	floodfill();
	MakeGraph();
	BFS();
	Ans=Dist[Target];
}
int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}