题目链接：1468 - Restaurant
题意：给定A，B公寓和一些餐馆坐标，要在要么比A或要么比B近的位置（曼哈顿距离）建新餐馆，问有几个位置。
思路：
由于A，B本身自带餐馆，所以答案肯定在A，B之间了，然后在AB之间每有一个点，就会有一些位置被限制掉，被限制掉的位置如图中红色区域。
这个区域比起两边都是高度不断多1的，并且上下是对称的。
所以可以先当成全在上面，for两遍，从左往右，从右往左，维护每个位置最小值即可，最后在统计和。
代码：< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include
#include
#include
using namespace std; #define INF 0x3f3f3f3f #define min(a,b) ((a)<(b) (a):(b)) #define max(a,b) ((a)>(b) (a):(b)) const int N = 60005; int t, n, m, h[N], y; struct Point { int x, y; void scan() { scanf("%d%d", &x, &y); } } p, a, b; int solve() { int i, ans = 0; h[a.x] = h[b.x] = 0; for (i = a.x + 1; i < b.x; i++) h[i] = min(h[i], h[i - 1] + 1); for (i = b.x; i > a.x; i--) h[i] = min(h[i], h[i + 1] + 1); for (i = a.x + 1; i < b.x; i++) if (h[i]) ans += min(h[i] - 1, y) + min(h[i] - 1, m - y - 1) + 1; return ans; } void init() { memset(h, INF, sizeof(h)); scanf("%d%d", &m, &n); a.scan(); b.scan(); y = a.y; if (a.x > b.x) swap(a.x, b.x); n -= 2; for (int i = 0; i < n; i++) { p.scan(); h[p.x] = min(h[p.x], abs(p.y - y)); } } int main() { scanf("%d", &t); while (t--) { init(); printf("%d\n", solve()); } return 0; }