题目大意：在一个w*h的格点区域内，有一些直线，定义一个点是危险点，如果它到某条直线的曼哈顿距离小于1；定义一个点是最安全点，如果它不是危险点，且到所有危险点的最小距离是最大的。如果所有点都是危险点，输出”MISS!”（STG中挂了一次称为1 miss），否则按字典序输出所有最安全点。
分析：首先得把危险点求出来，一个点到一条之间的曼哈顿最近点要么是它水平射线的交点（当直线斜率绝对值大于1时），要么是它垂直射线的交点（当直线斜率绝对值小于1时），证明比较显然。然后对于1000条直线，每条直线都可以用O(1000)的复杂度求出其“附近”的危险点，方法有很多种，但O(1000^2)的方法应该是会TLE的。有了这些危险点后，从这些点出发做一次bfs，求出所有点到危险点的距离，复杂度为O(1000^2)。如果最大的距离等于0，那么”MISS!”，否则就输出所有距离最大的点。
AC代码：
Accepted 3376 C++ 530 10112 代码 #include < iostream > #include < queue > #include < cassert > using namespace std; int d[ 1024 ][ 1024 ]; int gcd( int a, int b){ return b == 0 ? a:gcd(b,a % b);} int floor( int a, int b){ if (a < 0 ) return - ( ( - a + b - 1 ) / b); else return a / b;} int w,h; bool rx,ry,rxy; void mark( int x, int y){ if (rxy) swap(x,y); if (ry) y =- y; if (rx) x =- x; if ( 0 <= x && x < w && 0 <= y && y < h) d[x][y] = 0 ;} void gao( int w, int h, int x, int y, int dx, int dy){ if ((rx = (dx < 0 ))) w =- w, x =- x, dx =- dx; if ((ry = (dy < 0 ))) h =- h, y =- y, dy =- dy; if ((rxy = (dx < dy))) swap(w,h), swap(x,y), swap(dx,dy); int g = gcd(dx,dy); dx /= g; dy /= g; for ( int i = x; i < w || i <= 0 ; i ++ ) { int j = floor(y * dx + (i - x) * dy,dx); mark(i,j); if ((i - x) % dx != 0 ) mark(i,j + 1 ); }} int dir[ 4 ][ 2 ] = {{ 1 , 0 },{ - 1 , 0 },{ 0 , 1 },{ 0 , - 1 }}; int main(){ int n,x,y,dx,dy,i,j; while (scanf( " %d%d%d " , & w, & h, & n) != EOF) { assert( 3 <= w && w <= 1000 ); assert( 3 <= h && h <= 1000 ); memset(d, - 1 , sizeof (d)); for ( int k = 0 ;k < n;k ++ ) { scanf( " %d%d%d%d " , & x, & y, & dx, & dy); assert( 0 <= x && x < w); assert( 0 <= y && y < h); assert(dx != 0 || dy != 0 ); gao(w,h,x,y,dx,dy); } int maxd = 0 ; queue < pair < int , int > > q; for (i = 0 ;i < w;i ++ ) for (j = 0 ;j < h;j ++ ) if (d[i][j] == 0 ) q.push(make_pair(i,j)); while ( ! q.empty()) { x = q.front().first; y = q.front().second; q.pop(); for ( int k = 0 ;k < 4 ;k ++ ){ dx = x + dir[k][ 0 ]; dy = y + dir[k][ 1 ]; if ( 0 <= dx && dx < w && 0 <= dy && dy < h && d[dx][dy] ==- 1 ) { maxd = d[dx][dy] = d[x][y] + 1 ; q.push(make_pair(dx,dy)); } } } if (maxd == 0 ) puts( " MISS! " ); else { bool blank = false ; for (i = 0 ;i < w;i ++ ) for (j = 0 ;j < h;j ++ ) if (d[i][j] == maxd) { if (blank) putchar( ' ' ); blank = true ; printf( " (%d, %d) " ,i,j); } puts( "" ); } } return 0 ;}参考博客：http://watashi.ws/blog/1476/zojmonthly1008/
心得：下午比赛时也是用广搜+计算几何做的，当时被没有把所有的距离0点都入队，而是将射线经过的距离0的先入队，广搜是先判断与某点相邻的四个单位边是否与射线集相交，如果相交距离为0，否则为他前驱点距离+1。如果距离有缩小，则入队从新搜索，时间复杂度可想而知……
还是解题报告的方法好啊，先求出所有距离0点，统统入队，再进行宽搜，求出所有点到的射线集的最小曼哈顿距离。然后按字典序遍历距离数组，输出最安全的点，不能用快排的，不然会TLE的。
1.assert函数
2.swap函数
3.queue<pair<int,int> >的使用。
4.解题报告中floor函数的意义，表示不解，望大牛指点……
5.解题报告中求出所有距离0点的处理技巧，保证方向向量dx dy大于0，且dx >dy，否则进行交换。然后mark的时候要根据交换状态进行还原。
转载于:https://www.cnblogs.com/DreamUp/archive/2010/08/23/1806797.html
