Cod sursa(job #2649797)

Utilizator pregoliStana Andrei pregoli Data 16 septembrie 2020 14:16:24
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <bits/stdc++.h>
#define newline '\n'
#define STOP fout.close(); exit(EXIT_SUCCESS);
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
///******************************
#define x first
#define y second
typedef long long int64;
typedef pair<int64, int64> Point;
const int NMAX = 1e5 + 3;
int n, auxn;
Point p[NMAX], aux[NMAX];

void read() {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> p[i].x >> p[i].y;
}

void preCheck() {
    for (int i = 1; i < n; i++)
        if (p[i].x == p[i + 1].x && p[i].y == p[i + 1].y) {
            fout << 0 << newline;
            STOP
        }
}

inline int64 to2(int64 x) {
    return x * x;
}

inline int64 getDis(Point a, Point b) {
     return 1LL * to2(a.x - b.x) + 1LL * to2(a.y - b.y);
}

void pmerge(int l, int r) {
    int mid = (l + r) >> 1, i = l, j = mid + 1;
    auxn = 0;
    while (i <= mid && j <= r) {
        if (p[i].y < p[j].y)
            aux[++auxn] = p[i++];
        else if (p[i].y > p[j].y)
            aux[++auxn] = p[j++];
        else {
            if (p[i].x < p[j].x)
                aux[++auxn] = p[i++];
            else
                aux[++auxn] = p[j++];
        }
    }
    while (i <= mid)
        aux[++auxn] = p[i++];
    while (j <= r)
        aux[++auxn] = p[j++];
    for (j = 1, i = l; i <= r; i++, j++)
        p[i] = aux[j];
}

int64 getMinDis(int l, int r) {
    if (r - l + 1 == 3) {
        pmerge(l + 1, r);
        pmerge(l, r);
        return min(getDis(p[l], p[l + 1]), min(getDis(p[l], p[r]), getDis(p[l + 1], p[r])));
    }
    else if (r - l + 1 == 2) {
        pmerge(l, r);
        return getDis(p[l], p[r]);
    }
    int mid = (l + r) >> 1;
    int64 minDis = min(getMinDis(l, mid), getMinDis(mid + 1, r));
    pmerge(l, r);
    auxn = 0;
    for (int i = l; i <= r; i++)
        if (to2(p[mid].x - p[i].x) <= minDis)
            aux[++auxn] = p[i];
    for (int i = 1; i <= auxn; i++)
        for (int j = i + 1; j - i + 1 <= 9 && j <= auxn; j++)
            minDis = min(minDis, getDis(aux[i], aux[j]));
    return minDis;
}

int main() {
    read();
    sort(p + 1, p + n + 1);
    preCheck();
    fout << setprecision(6) << fixed << sqrt(getMinDis(1, n));//*/
    STOP
}