一下所说的距离皆为哈密顿距离
如果一个点X对于任意的已知点Y,要么X比Y距离A近, 要么X比Y距离B近,则X是一个合法点,求合法点的个数,
因为在A,B点分别有一个餐厅,而且A,B点的纵坐标相同,所以A.x左边和B.x右边的点都不合法,而假设此时只有A,B俩点,则合法点如下图所示(实点为合法点)
从中不难发现规律
现在假设一个点X在AB连线的上方,则X所限制的合法区域为
所以可以对A.x到B.x的横坐标进行扫描,找出每个横坐标出现的大于A.y最小纵坐标和小于A.y的最大横坐标,然后分别从左右俩个方向扫描合法区域,最后统计合法点数有以小细节容易出错,在注释中给出
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::istringstream; using std::make_pair; using std::greater; const int MAXM(60010); const int INFI((INT_MAX-1) >> 1); int miy[MAXM], mxy[MAXM], Y[MAXM]; int main() { int T; int m, n; scanf("%d", &T); int x1, y1, x2, y2, tx, ty; while(T--) { scanf("%d%d", &m, &n); scanf("%d%d%d%d", &x1, &y1, &x2, &y2); if(x1 > x2) { swap(x1, x2); swap(y1, y2); } for(int i = x1+1; i < x2; ++i) { miy[i] = INFI; mxy[i] = -INFI; } for(int i = 2; i < n; ++i) { scanf("%d%d", &tx, &ty); if(ty >= y1) miy[tx] = min(miy[tx], ty); if(ty <= y1) mxy[tx] = max(mxy[tx], ty); } Y[x1] = 0; for(int i = x1+1; i < x2; ++i) Y[i] = min(miy[i]-y1, y1-mxy[i]); for(int i = x1+1; i < x2; ++i) Y[i] = min(Y[i-1]+1, Y[i]); Y[x2] = 0; for(int i = x2-1; i > x1; --i) Y[i] = min(Y[i+1]+1, Y[i]); long long ans = 0LL; for(int i = x1+1; i < x2; ++i) if(Y[i]) { ++ans; ans += min(Y[i]-1, m-1-y1); //注意要考率纵坐标上下限 ans += min(Y[i]-1, y1); } printf("%lld\n", ans); } return 0; }