Cod sursa(job #3031833)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 20 martie 2023 21:08:42
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <bits/stdc++.h>
#include <fstream>
#define nmax 100005
#define x first
#define y second
#define epsilon 1e4
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
pair <int, int> points[nmax];
int n;
long long mindist;
long long getPointsDist(pair<int, int> a, pair<int, int> b) {
    return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.y != b.y) {
        return a.y > b.y;
    }
    return a.x < b.x;
}
long long getMinDist(int startPoint, int stopPoint) {
    if (stopPoint == startPoint) {
        return 8e18;
    }
    if (stopPoint == startPoint + 1) {
        return getPointsDist(points[startPoint], points[stopPoint]);
    }
    int mid = (startPoint + stopPoint) >> 1;
    long long crtMinDist = min( getMinDist(startPoint, mid), getMinDist(mid + 1, stopPoint));
    long double actualMinDist = sqrt(crtMinDist * 1.0);
    int d = points[mid].x;
    vector <pair<int, int> > left, right;
    for (int i = startPoint; i <= mid; i++) {
        if (abs(points[i].x + actualMinDist -d) <= epsilon) {
            left.push_back(points[i]);
        }
    }
    for (int i = mid + 1; i <= stopPoint; i++) {
        if (abs(points[i].x - actualMinDist - d) <= epsilon) {
            right.push_back(points[i]);
        }
    }
    sort(left.begin(), left.end(), cmp);
    sort(right.begin(), right.end(), cmp);
    int top = 0;
    for (auto rightPoint : right) {
        while(top < left.size()) {
            if (abs(left[top].y - actualMinDist - rightPoint.y) <= epsilon) {
                break;
            } else {
                top++;
            }
        }
        if (top == left.size()) {
            break;
        }
        for (int pos = top; pos < left.size(); pos++) {
            if (abs(left[pos].y + actualMinDist - rightPoint.y) <= epsilon) {
                break;
            }
            crtMinDist = min(crtMinDist, getPointsDist(left[pos], rightPoint));
        }
    }
    return crtMinDist;
}

int main() {
    fin>>n;
    for (int i = 1; i <= n; i++) {
        fin>>points[i].x>>points[i].y;
    }
    sort(points + 1, points + n + 1);
    mindist = getMinDist(1,n);
    fout<<setprecision(12)<<sqrt(mindist * 1.0);
}