题解 P1429 【平面最近点对（加强版）】

shame_djj · 2019-07-07 10:09:16 · 题解

我的是一种玄学算法：

直接找

按照横纵坐标，排个序

对于每一个点，往后找k个点（这个k自己定）

本题n是二十万，常数小点的话能把k升到100

（本题数据水爆了，我在k=5时就A了这道题）

每回，更新ans

其实就是稍微优化一下O(n2)做法

代码好简单的

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

struct point {double x, y;} a[200010];
double dist (point a, point b) {return sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}
bool cmp (point a, point b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
double ans = (1 << 30) + 0.01;
int n;

int main() {
    scanf ("%d", &n);
    for (register int i = 1; i <= n; i ++)
        scanf ("%lf%lf", &a[i].x, &a[i].y);
    sort (a + 1, a + n + 1, cmp);
    for (register int i = 1; i < n; i ++) {
        for (register int j = 1; j <= 5; j ++)//所谓的k
            ans = min (ans, dist(a[i], a[i + j]));
    }
    printf ("%.4lf\n", ans);
    return 0;
}

我的做法，肯定是错的（滑稽）

但是，在考试时，我们拿十分钟给第二题拿了80以上的分数

我个人认为，是很值得的（反正本蒟蒻考试时稍难点的题总是花好长时间，还经常炸锅）

（何况这题本来100也就是很极限的数据了，也就差不多了）

离Noip还有一百来天，大家加油(/@"A"@)/