AcWing 1660. 社交距离 II
原题链接
简单
作者:
RainSure
,
2022-02-16 09:58:03
,
所有人可见
,
阅读 205
找出半径的最大值, 然后找出生病的牛的连通块 只要二者距离$\leq$ R,就算连通
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1010;
#define x first
#define y second
typedef pair<int,int> PII;
PII a[maxn];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i ++){
cin >> a[i].x >> a[i].y;
}
sort(a, a + n);
int r = 1e9;
for(int i = 0; i < n - 1; i ++){
if(a[i].y != a[i + 1].y) r = min(r, a[i + 1].x - a[i].x);
}
r -= 1;
int cnt = 0;
for(int i = 0; i < n; i ++){
if(a[i].y == 0) continue;
int j = i + 1;
while(j < n && a[j].x - a[j - 1].x <= r) j ++;
i = j - 1;
cnt ++;
}
cout << cnt << endl;
return 0;
}