NC25220. Manhattan
描述
MINIEYE's engineer M has designed a game recently.
There are two races A and B in the game and both of them can only appear on the integral points in the two-dimensional space. Characters of the same race have same eyesight, the eyesight for race A is Sa, for race B is Sb. If the Manhattan distance from character 1 to character 2 is within character 1's eyesight, then character 1 can see character 2.
The method to calculate the Manhattan distance between the two characters is: if the coordinate of character 1 is (x1,y1) and character 2 is (x2,y2), then the Manhattan distance between them is：|x2 - x1 | + |y2 - y1|.
If character 1 can see character 2, it means character 1 knows where character 2 is. Besides, a character can share with other characters of the same race about where the characters of the other race are if they can see each other.
To find a balance in the game, M hopes that：
1.Any characters from race A can know the position of any characters from race B.
2.There's a character from race B who doesn't know the position of a character from race A.
3. Sb > Sa.
M needs your help to analyze whether there are non-negative integers Sa and Sb that can meet the above balance requirements?
输入描述
The first row of the input are two integers n and m(1 ≤ n, m ≤ 1000) separated by space, n and m respectively represents the character numbers of the two races.
For the following n rows, each row has two integers x and y separated by space to represent the coordinate of a character from race A.
And for another m rows, x and y represent the coordinate of a character from race B.
It’s guaranteed that -1000 ≤ x, y ≤ 1000.
输出描述
Output one row which includes an integer. If suitable Sa and Sb are found, then output 1, otherwise output 0.
示例1
输入:
3 2 -4 0 0 0 4 0 -3 0 3 0
输出:
1
C++11(clang++ 3.9) 解法, 执行用时: 125ms, 内存消耗: 1508K, 提交时间: 2019-04-22 19:40:15
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
int pre[maxn];
bool vis[maxn][maxn];
struct point{int x, y; }a[maxn], b[maxn];
int dis(point &a, point &b) {return abs(a.x - b.x) + abs(a.y - b.y); }
int Find(int x) {return x == pre[x] ? x : pre[x] = Find(pre[x]); }
bool check(int S, point a[], point b[], int n, int m)
{
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
vis[i][j] = dis(a[i], b[j]) <= S;
for(int i = 0; i < n; i++) pre[i] = i;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
if(dis(a[i], a[j]) > S) continue;
int u = Find(i), v = Find(j);
if(u == v) continue;
pre[u] = v;
for(int k = 0; k < m; k++) vis[v][k] |= vis[u][k];
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(!vis[Find(i)][j]) return false;
return true;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d%d", &a[i].x, &a[i].y);
for(int i = 0; i < m; i++) scanf("%d%d", &b[i].x, &b[i].y);
int l = 0, r = 5000, sa = 5000;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid, a, b, n, m)) r = mid - 1, sa = mid;
else l = mid + 1;
}
printf("%d\n", !check(sa + 1, b, a, m, n));
return 0;
}