最接近点对问题
typedef long long ll;
const int N = 1e5 + 10;
struct node {
ll x[2];
}a[N], b[N];
int now, n;
ll ans;
map<pair<ll, ll>, int> mp;
bool cmp(node a, node b) { return a.x[now] < b.x[now]; }
ll sqr(int x) { return (ll)x * x; }
ll dis(node a, node b) { return sqr(a.x[0] - b.x[0]) + sqr(a.x[1] - b.x[1]); }
void build(int l, int r, int d) {
if(l >= r) return ;
int m = (l + r) >> 1;
now = d;
nth_element(a + l, a + m, a + r, cmp);
build(l, m, d ^ 1);
build(m + 1, r, d ^ 1);
}
void query(int l, int r, int d, node p) {
if(l >= r) return ;
int m = (l + r) >> 1;
int ql = l, qr = m;
ll res = dis(a[m], p);
if(ans == 0 || res && ans > res) ans = res;
if(p.x[d] > a[m].x[d]) ql = m + 1, qr = r;
query(ql, qr, d ^ 1, p);
if(ans > sqr(a[m].x[d] - p.x[d]))
query(l + m - ql + 1, m + r - qr, d ^ 1, p);
}
void solve() {
scanf("%d",&n);
ll sum = 5e18;
for(int i = 0;i < n; i++) {
scanf("%lld %lld",&a[i].x[0],&a[i].x[1]);
if(mp[{a[i].x[0], a[i].x[1]}]) sum = 0;
else mp[{a[i].x[0], a[i].x[1]}]++;
b[i] = a[i];
}
build(0, n, 0);
for(int i = 0;i < n; i++) {
ans = 0;
query(0, n, 0, b[i]);
sum = min(ans, sum);
}
printf("%.4lf\n",sqrt(1.0 * sum));
}
最后更新:
2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42