Cod sursa(job #2639362)

Utilizator irimia_alexIrimia Alex irimia_alex Data 1 august 2020 16:48:19
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define EPSILON 1e-17
#define INF 1e9

using namespace std;

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

struct point {
    int x, y;
};

vector<point> vec;

bool cmpX(const point& a,const point& b) {
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

bool cmpY(const point& a,const point& b) {
	if (a.y == b.y) return a.x < b.x;
	return a.y < b.y;
}

double dist(point a, point b) {
	long long int x = a.x - b.x;
	long long int y = a.y - b.y;
	x *= x;
	y *= y;
	return sqrt(x + y);
}

double closestPair(vector<point>& vec) {
	sort(vec.begin(), vec.end(), cmpX);
	set<point, decltype(cmpY)*> s(cmpY);
	set<point, decltype(cmpY)*>::iterator it;
	int i = 0;
	double d = INF;
	for (int j = 0;j < vec.size();++j) {
		while (i<j && vec[j].x - vec[i].x>d) {
			s.erase(vec[i]);
			++i;
		}
		s.insert(vec[j]);
		it = s.find(vec[j]);
		set<point, decltype(cmpY)*>::iterator succ = next(it);
		while (succ != s.end() && (*succ).y - vec[j].y < d) {
			if (dist((*succ), vec[j]) < d) d = dist((*succ), vec[j]);
			succ = next(succ);
		}
		set<point, decltype(cmpY)*>::iterator pred = prev(it);
		while (pred != s.end() && vec[j].y - (*pred).y < d) {
			if (dist((*pred), vec[j]) < d) d = dist((*pred), vec[j]);
			pred = prev(pred);
		}
	}

	return d;
}

int main()
{
	int n;
	fin >> n;
    int x, y;
    while (n--) {
        fin >> x >> y;
        vec.push_back({ x,y });
    }
	fout << fixed << setprecision(6);
	fout<<closestPair(vec);

    return 0;
}