Posted in日常

P1429-平面最近点对（加强版）

2024年4月12日

题目传送门

点我

题目思路

分治做，从中间劈开

然后在合并时需要讨论两个区间之间因为有分别各出一个点导致的最小值更新问题

提交之后全错，，，，fuck

然后发现是精度问题，万恶的cout，需要手动强制精度：

    cout << fixed << setprecision(4) << fz(v, 0, n - 1);

然后错了67910四个点，草

结果看讨论区，发现点还能重复？？？？

好吧，是我输了

警钟撅烂

AC代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>

using namespace std;

double dis(pair<double, double> a, pair<double, double> b)
{
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

double fz(vector<pair<double, double>> &v, int l, int r)
{
    int mid = (l + r) / 2;
    if (l == r)
        return 0.0;
    else if (l + 1 == r)
        return dis(v[l], v[r]);
    double m1 = fz(v, l, mid);
    double m2 = fz(v, mid + 1, r);
    if (m1 != 0 && m2 != 0)
    {
        double m = min(m1, m2);
        int tl = mid;
        int tr = mid + 1;
        while (tl >= l && v[mid].first - v[tl].first < m)
            tl--;
        while (tr <= r && v[tr].first - v[mid + 1].first < m)
            tr++;
        vector<double> v1;
        v1.push_back(m);
        for (int i = tl; i < tr; i++)
            for (int j = i + 1; j <= tr; j++)
                v1.push_back(dis(v[i], v[j]));
        sort(v1.begin(), v1.end());
        return v1[0];
    }
    else if (m1 == 0 && m2 != 0)
    {
        int tl = l;
        int tr = l + 1;
        while (tr <= r && v[tr].first - v[l + 1].first < m2)
            tr++;
        vector<double> v1;
        v1.push_back(m2);
        for (int i = tl; i < tr; i++)
            for (int j = i + 1; j <= tr; j++)
                v1.push_back(dis(v[i], v[j]));
        sort(v1.begin(), v1.end());
        return v1[0];
    }
    else if (m2 == 0 && m1 != 0)
    {
        int tl = r - 1;
        int tr = r;
        while (tl >= l && v[r - 1].first - v[tl].first < m1)
            tl--;
        vector<double> v1;
        v1.push_back(m1);
        for (int i = tl; i < tr; i++)
            for (int j = i + 1; j <= tr; j++)
                v1.push_back(dis(v[i], v[j]));
        sort(v1.begin(), v1.end());
        return v1[0];
    }
    else if (m1 == 0 && m2 == 0)
        return dis(v[l], v[r]);
    return 0.0;
}

int main()
{
    int n;
    cin >> n;
    vector<pair<double, double>> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i].first;
        cin >> v[i].second;
    }
    sort(v.begin(), v.end(), [](pair<double, double> a, pair<double, double> b)
         { return a.first < b.first; });
    for (int i = 1; i < n; i++)
        if (v[i].first == v[i - 1].first && v[i].second == v[i - 1].second)
        {
            cout << "0.0000";
            return 0;
        }
    cout << fixed << setprecision(4) << fz(v, 0, n - 1);
    return 0;
}
Tags: