POJ 2903 Joy of Mobile Routing

 

/*

从没做过这么复杂的计算几何题，做得我好几次想quit，最后还是坚持写了下来，前前后后花了一天多时间

其实思想还是比较简单的，就是求出所有可以被信号覆盖的点，然后对这些点按照给定的源点和终点进行BFS.

所以难点就在于怎么判断哪些点可以被信号覆盖，主要有以下两点考虑

 

 (1)天线可以覆盖和它在同一行，同一列的点

 (2)对于(1)中未被覆盖的点需要进行额外判断，判断从这点抬头是否可以看到任意一根天线，如果可以即被覆盖

 

第二步的代码书写是最为复杂，因为需要判断当前点与天线的连线与哪些block相交，且是否有相交的block阻挡了

这条线，具体判断方法是：枚举这两点之间的所有block，先判断当前block与连线在平面上是否相交，如果相交，

求出连线与block四条边交点在连线上的高度，如果这个高度小于当前block高度，则block会阻挡信号，即这个天线

不能覆盖当前点

*/

 

 

#include <iostream>
#include <cmath>
#define maxv(a, b) ((a) >= (b) ? (a) : (b))
#define minv(a, b) ((a) <= (b) ? (a) : (b))
#define MAX_N 55
#define MAX_A 105
#define MAX_Q (MAX_N * MAX_N)
using namespace std;

//记录所有的intersection
struct node
{
	int type;	//1: 当前点可以被信号覆盖, 0:当前点不可以被信号覆盖
	int h;      //当前点右下方block的高度
	bool v;     //用于bfs是标识当前点是否被访问过
}nodes[MAX_N][MAX_N];

//记录位置的结构
struct pos
{
	int r, c, h;   //当前位置的行列号，如果这个位置用来表示block或者天线，则还有一个高度信息
};

int R, C, caseN;   //输入图的行列数以及用例个数
int atnum;         //天线个数
pos ats[MAX_A];    //记录天线的信息

pos sp, ep;        //起点和终点

//bfs时队列结构
struct elem
{
	int r, c;
	int step;
};
//bfs队列
elem bfsq[MAX_Q + 1];
int head, tail;

//可以走的四个方向
int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

//判断当前格子是否为合法格子(没有越界)
bool legalStep(int r, int c)
{
	return r >= 0 && r <= R && c >= 0 && c <= C;
}

//bfs算法，从起点走信号点寻找终点
int bfs()
{
	bool found = false;
	head = tail = 1;
	nodes[sp.r][sp.c].v = true;
	bfsq[tail].r = sp.r; bfsq[tail].c = sp.c; bfsq[tail].step = 0;
	tail = tail % MAX_Q + 1;

	while(head != tail)
	{
		int curR = bfsq[head].r, curC = bfsq[head].c, curStep = bfsq[head].step;
		head = head % MAX_Q + 1;
		//找到终点
		if(curR == ep.r && curC == ep.c) 
		{
			found = true;
			return curStep * 10;
		}
		int newR, newC, newStep;
		//走四个方向
		for(int d = 0; d < 4; d++)
		{
			newR = curR + dir[d][0]; newC = curC + dir[d][1]; newStep = curStep + 1;
			//判断当前方向是否可走
			if(legalStep(newR, newC) && !nodes[newR][newC].v && (nodes[newR][newC].type == 1 || (newR == ep.r && newC == ep.c)))
			{
				nodes[newR][newC].v = true;
				bfsq[tail].r = newR;
				bfsq[tail].c = newC;
				bfsq[tail].step = newStep;
				tail = tail % MAX_Q + 1;
			}
		}
	}
	//无法到达
	if(!found) return -1;
}

//差积
int cross(const pos &p1, const pos &p2, const pos &p3)
{
	return (p3.c * 10 - p1.c * 10) * (p2.r * 10 - p1.r * 10) - (p2.c * 10 - p1.c * 10) * (p3.r * 10 - p1.r * 10);
}

//判断直线[lp11, lp12]与[lp21, lp22],是否相交
bool intersect(const pos &lp11, const pos &lp12, const pos &lp21, const pos &lp22)
{
	int v1 = cross(lp11, lp12, lp21);
	int v2 = cross(lp11, lp12, lp22);
	int v3 = cross(lp21, lp22, lp11);
	int v4 = cross(lp21, lp22, lp12);

	return v1 * v2 < 0 && v3 * v4 < 0;
}

//判断天线a是否可以覆盖点p
bool canReach(const pos &a, const pos &p)
{
	int r, c;
	pos temp1, temp2, temp3, temp4;

	//直线[a, p]的表示

	//直线[a, p]的效率
	double av = (double)(a.r * 10 - p.r * 10) / (double)(a.c * 10 - p.c * 10);
	//直线[a, p]在y轴上的截距离
	double dv = a.r * 10 - av * a.c * 10;

	//点a, p之间的距离
	double dist1 = sqrt(double((a.r * 10 - p.r * 10) * (a.r * 10 - p.r * 10) + (a.c * 10 - p.c * 10) * (a.c * 10 - p.c * 10)));
	double dist2;
	double h = a.h;

	//遍历点a, p之间的block
	for(r = minv(a.r, p.r); r < maxv(a.r, p.r); r++)
	{
		for(c = minv(a.c, p.c); c < maxv(a.c, p.c); c++)
		{
			//取当前block的四个点
			temp1.r = r; temp1.c = c;
			temp2.r = r + 1; temp2.c = c + 1;
			temp3.r = r + 1; temp3.c = c;
			temp4.r = r; temp4.c = c + 1;

			//判断直线[a, p]是否与block[temp1, temp2, temp3, temp4]相交，用到了差积
			if((intersect(a, p, temp1, temp2) || intersect(a, p, temp3, temp4)))
			{
				//分别计算直线[a, p]与当前block四条边所在直线交点的横纵坐标，并判断这个点是否在这个block的边上，如果是则利用等比关系计算当前点在直线[a, p]上的高度，
				//如果这个高度小于当前block的高度，则被阻挡
				double x, y;
				//block的上边
				y = r * 10; x = (y * 10 - dv) / av;
				if(x >= c * 10 && x <= (c + 1) * 10)
				{
					dist2 = sqrt(double((y - p.r * 10) * (y - p.r * 10) + (x - p.c * 10) * (x - p.c * 10)));
					double newh = h * dist2 / dist1;
					if(newh < nodes[r][c].h) return false;
				}
				//block的下边
				y = (r + 1) * 10; x = (y - dv) / av;
				if(x >= c * 10 && x <= (c + 1) * 10)
				{
					dist2 = sqrt(double((y - p.r * 10) * (y - p.r * 10) + (x - p.c * 10) * (x - p.c * 10)));
					double newh = h * dist2 / dist1;
					if(newh < nodes[r][c].h) return false;
				}
				//block的左边
				x = c * 10; y = av * x + dv;
				if(y >= r * 10 && y <= (r + 1) * 10)
				{
					dist2 = sqrt(double((y - p.r * 10) * (y - p.r * 10) + (x - p.c * 10) * (x - p.c * 10)));
					double newh = h * dist2 / dist1;
					if(newh < nodes[r][c].h) return false;
				}
				//block的右边
				x = (c + 1) * 10; y = av * x + dv;
				if(y >= r * 10 && y <= (r + 1) * 10)
				{
					dist2 = sqrt(double((y - p.r * 10) * (y - p.r * 10) + (x - p.c * 10) * (x - p.c * 10)));
					double newh = h * dist2 / dist1;
					if(newh < nodes[r][c].h) return false;
				}
			}
		}
	}
	//可以覆盖
	return true;
}

//预处理，计算所有点是否可以被覆盖
void preProcess()
{
	int i, j, k;
	pos temp;
	//所有天线所在的横纵轴上的点都可以被覆盖
	for(k = 0; k < atnum; k++)
	{
		for(i = 0; i <= C; i++) nodes[ats[k].r][i].type = 1;
		for(j = 0; j <= R; j++) nodes[j][ats[k].c].type = 1;
	}

	//对于上面不和天线在一条横纵线上的点，判断从当前点是否可以看到某个天线的最高点而不被block阻挡
	for(i = 0; i <= R; i++)
	{
		for(j = 0; j <= C; j++)
		{
			if(nodes[i][j].type == 1) continue;
			temp.r = i; temp.c = j;
			for(k = 0; k < atnum; k++)
			{
				if(canReach(ats[k], temp))
				{
					nodes[i][j].type = 1;
					break;
				}
			}
		}
	}


}

int main()
{
	//ofstream output("output.txt");
	int i, j;
	scanf("%d", &caseN);
	while(caseN--)
	{
		scanf("%d%d", &R, &C);
		memset(nodes, 0, sizeof(nodes));
		for(i = 0; i < R; i++)
			for(j = 0; j < C; j++)
				scanf("%d", &nodes[i][j].h);
		scanf("%d%d%d%d", &sp.r, &sp.c, &ep.r, &ep.c);
		scanf("%d", &atnum);
		for(i = 0; i < atnum; i++) scanf("%d%d%d", &ats[i].r, &ats[i].c, &ats[i].h);
		
		preProcess();
		
		cout<<bfs()<<endl;
	}

	
	return 0;
}