【bzoj2304】[APIO2011]寻路path

2014年8月5日3,2280

Description

TooDee是一块二维格子状的土地(就像著名的笛卡尔坐标系那样) ,在这里
生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物,它们只在二维活动,而且
它们非常的文明开化。TooDee 的蜂窝和正常世界的蜂窝也是很不一样的,它们
是矩形的且它们的边平行于TooDee的地理坐标系,就是说矩形的边或者是东西
走向,或者是南北走向。
因为 Dees 是很高级的生物,它们有很多固定的飞行轨道,这些轨道由一些
平行于坐标轴的线段组成,线段只会在经纬度都是整数的点相交。 Dee在TooDee
飞行时必须遵守以下规则(请记住TooDee中所有点的经纬度都是整数):
1  如果当前在点(XS, YS), 则下步只能飞到四个邻点  (XS, YS – 1), (XS, YS + 1),
(XS – 1, YS ), (XS + 1, YS );
2  不可以进入蜂巢;
3  只能在蜂巢的角或者边上改变飞行方向;
4  开始的时候可以向任何方向飞;
今晚是公共财政大臣Deeficer的女儿的生日,她想尽早回家,请帮她找到最
快的回家路径。假设她每秒可以飞行一个单位的距离。

Input

每个测试点包含多组数据。
输入的第一行包含一个整数T,表示测试数据的组数。接下来依次描述这T
组数据,相邻的两组之间使用一个空行分隔。测试数据不多于20组。
对于每组数据,第一行包含4个整数 xs, ys, xt, yt,表示Deeficer 的办公室和
家的坐标分别为(xs, ys)和(xt, yt)。第二行包含一个整数n,表示蜂巢的个数。接下
来的n行描述所有的蜂巢,其中第 i行包含 4 个整数xi1,  yi1,  xi2,  yi2,表示第i个
蜂巢两个对角的坐标分别为(xi1, yi1)和(xi2, yi2)。
任何两个蜂巢都不会相交,也不会接触(在角上也不会接触)。办公室和家
处在不同的位置。每个蜂巢的面积为正。

Output

对于每一组数据,输出一个整数,表示Deeficer 最快回家的时间(单位为秒),
如果她无法按规则回家,则输出“No Path”。

对于100%的测试数据,1 ≤ n ≤ 1000,所有坐标都是不超过10^9
的整数;

Sample Input

2
1 7 7 8
2
2 5 3 8
4 10 6 7
2 1 5 4
1
3 1 4 3

Sample Output

9
No Path

题解

http://wenku.baidu.com/link?url=xJBtwotOM1MjW38-sIQUydPsyCFpCmcuYGIpCCzEhDnyJnpa7cQ_7JmcH1IbZ0rsLKF_bST0jQu2xSDb55755lvsedIqzu0kT32S8FXWB_7

n^2的做法。。。bzoj数据太强了根本过不去。。。

暴力大概就是上下左右扫描乱找

正解TMD我写了两遍用了n个小时T T

题解中只有几句话,简直了说起来似乎很简单,但是问题会比较多T T

例如这个新建的点是要上下延伸的,这我没有想到很好的办法,只能再对于每个xy坐标建个平衡树,每次把点放进去找相同x/y坐标的最近点

对于起点和终点的处理T T,如果当做矩形的话那么起点终点落在边或者角上是不好处理的

那么可以暴力找他们最近的矩形,类似上面一样连边,注意特判起点可以直接到终点的情况

然后最短路用dijkstra

记得vfk似乎说过这道题代码超过6k的都是弱菜,好吧我超过了