Cod sursa(job #2054219)

Utilizator Data 1 noiembrie 2017 19:47:45 Cele mai apropiate puncte din plan 85 cpp done Arhiva educationala 3.39 kb
``````#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

inline long long sqr(int x) {
return 1LL * x * x;
}

class Point {

public:

int x, y;

Point(){}
Point(int x, int y) {
this->x = x;
this->y = y;
}

friend istream& operator>> (istream& in, Point& a) {
in >> a.x >> a.y;
}

friend bool operator< (const Point a, const Point b) {
return a.x < b.x;
}

friend long long dist(const Point a, const Point b) {
return sqr(a.x - b.x) + sqr(a.y - b.y);
}
};

vector<Point> puncteX, puncteY, middlePoints, aux;

void customMerge(int st, int mid, int dr, int lineX, long long d) {

int i = st, j = mid + 1;

aux.clear();
while (i <= mid && j <= dr) {

if (puncteY[i].y <= puncteY[j].y) {

if (1LL * lineX - puncteY[i].x < d)
middlePoints.push_back(puncteY[i]);

aux.push_back(puncteY[i]);
++i;
}
else {

if (1LL * puncteY[j].x - lineX < d)
middlePoints.push_back(puncteY[j]);

aux.push_back(puncteY[j]);
++j;
}
}

while (i <= mid) {

if (1LL * lineX - puncteY[i].x < d)
middlePoints.push_back(puncteY[i]);

aux.push_back(puncteY[i]);
++i;
}

while (j <= dr) {

if (1LL * puncteY[j].x - lineX < d)
middlePoints.push_back(puncteY[j]);

aux.push_back(puncteY[j]);
++j;
}

for (int i = st, j = 0; j < aux.size(); ++i, ++j) {
puncteY[i] = aux[j];
}
}

inline void printState(int st, int dr, long long value, int depth) {

for (int i = 1; i <= depth; ++i)
cerr << "\t";

if (value == -1) {
cerr << "Begin: [" << st << ", " << dr << "]\n";
}
else {
cerr << "End: [" << st << ", " << dr << "] -> " << value << "\n";
}

}

long long closestPoints(int st, int dr, int t) {

//    printState(st, dr, -1, t);

if (st >= dr) {
//        printState(st, dr, 1LL * 1e18, t);
return 1LL * 1e18;
}
if (st + 1 == dr) {
if (puncteY[st].y > puncteY[dr].y) {
swap(puncteY[st], puncteY[dr]);
}

//        printState(st, dr, dist(puncteX[st], puncteX[dr]), t);
return dist(puncteX[st], puncteX[dr]);
}

int mid = (st + dr) >> 1;

long long d1 = closestPoints(st, mid, t + 1);
long long d2 = closestPoints(mid + 1, dr, t + 1);
long long d = min(d1, d2);

customMerge(st, mid, dr, puncteX[mid].x, d);

for (int i = 0; i < middlePoints.size(); ++i) {
int go = min(i + 8, (int)middlePoints.size() - 1);
for (int j = i + 1; j <= go ; ++j) {
d = min(d, dist(middlePoints[i], middlePoints[j]));
}
}
middlePoints.clear();
//    printState(st, dr, d, t);

return d;
}

int main() {

int n;

fin >> n;

puncteX.resize(n);
puncteY.resize(n);

for (int i = 0; i < n; ++i) {
fin >> puncteX[i];
puncteY[i] = puncteX[i];
}

sort(puncteX.begin(), puncteX.end());

fout << fixed << setprecision(7) << sqrt(closestPoints(0, n - 1, 0));

return 0;
}
``````