Pagini recente » Cod sursa (job #2344914) | Cod sursa (job #781152) | Cod sursa (job #1053089) | Cod sursa (job #2264331) | Cod sursa (job #2054246)
/*
* Metoda Divide et Impera
* Varianta 3, Problema 4
*
* Autorul sursei: Dospra Cristian, grupa 235
*/
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const long long INF = 1LL * 2e18;
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> puncte, middlePoints, aux;
/*
* puncte: punctele date
* middlePoints: punctele aflate la un momentdat la distanta < delta in stanga si dreapta liniei de separare
* aux: auxiliar pentru interclasare
*/
//ordonez punctele crescator dupa ordonata
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 (puncte[i].y <= puncte[j].y) {
if (1LL * lineX - puncte[i].x < d)
middlePoints.push_back(puncte[i]);
aux.push_back(puncte[i]);
++i;
}
else {
if (1LL * puncte[j].x - lineX < d)
middlePoints.push_back(puncte[j]);
aux.push_back(puncte[j]);
++j;
}
}
while (i <= mid) {
if (1LL * lineX - puncte[i].x < d)
middlePoints.push_back(puncte[i]);
aux.push_back(puncte[i]);
++i;
}
while (j <= dr) {
if (1LL * puncte[j].x - lineX < d)
middlePoints.push_back(puncte[j]);
aux.push_back(puncte[j]);
++j;
}
for (int i = st, j = 0; j < aux.size(); ++i, ++j) {
puncte[i] = aux[j];
}
}
//solve divide et impera: la coborare punctele sunt sortate dupa abscisa, in urcare sunt sortate dupa ordonata
long long closestPoints(int st, int dr) {
//daca am un singur punct nu pot da o distanta
if (st >= dr) {
return INF;
}
//daca am doua puncte (caz elementar) returnez distanta dintre ele
if (st + 1 == dr) {
//le ordonez dupa y
if (puncte[st].y > puncte[dr].y)
swap(puncte[st], puncte[dr]);
return dist(puncte[st], puncte[dr]);
}
int mid = (st + dr) >> 1;
//luam cea mai buna distanta din partea stanga si cea dreapta
long long d1 = closestPoints(st, mid);
long long d2 = closestPoints(mid + 1, dr);
long long d = min(d1, d2);
//sortam dupa ordonata si incercam sa vedem daca putem imbunatati folosind un punct din stanga respectiv unul din dreapta liniei de separare
customMerge(st, mid, dr, puncte[mid].x, d);
//pentru fiecare punct aflat la distanta maxim d de linia separatoare (pe abscisa)
for (int i = 0; i < middlePoints.size(); ++i) {
int go = min(i + 8, (int)middlePoints.size() - 1); //stiu ca pot exista maxim 7 puncte la distanta < d pe ordonata
for (int j = i + 1; j <= go ; ++j) {
d = min(d, dist(middlePoints[i], middlePoints[j])); //le verific
}
}
middlePoints.clear();
return d;
}
int main() {
int n;
//citire
fin >> n;
puncte.resize(n);
for (int i = 0; i < n; ++i) {
fin >> puncte[i];
}
//sortam dupa abscisa
sort(puncte.begin(), puncte.end());
//afisare
fout << fixed << setprecision(7) << sqrt(closestPoints(0, n - 1));
return 0;
}