Pagini recente » Cod sursa (job #2057628) | Cod sursa (job #2456818) | Cod sursa (job #2133642) | Cod sursa (job #2600391) | Cod sursa (job #2496463)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef pair <double, double> point; //punct 2D
const int MAXN = 100010; //constanta
const double INF = 1e16; //constanta
const int PRECISION = 6; //pentru afisare cu 6 zecimale
vector <point> Vy(MAXN);
vector <point> V(MAXN);
vector <point> final_interclasare(MAXN);
int N;
//functie pentru distanta dintre 2 puncte
double dist(point p1, point p2) {
return sqrt((p1.first - p2.first) * (p1.first - p2.first) +
(p1.second - p2.second) * (p1.second - p2.second));
}
//functie pentru compararea bruta a maxim 3 puncte
double bruteForce(int from, int to) {
double minDist = INF;
for (int i = from; i <= to; i++)
for (int j = i + 1; j <= to; j++)
minDist = min(minDist, dist(V[i], V[j]));
return minDist;
}
//sortare bruteForce
void sort_BruteForce(int left, int right) {
for (int i = left; i <= right; i++)
for (int j = i + 1; j <= right; j++)
if (Vy[i] > Vy[j])
swap(Vy[i], Vy[j]);
}
//functie unde aflam rezultatul final
double closestOverlapping(vector <point>& strip, double minDist) {
//aici aflam distanta minima dintre cele maxim 8 puncte din vectorul strip
for (int i = 0; i < strip.size(); i++) {
for (int j = i + 1; j < strip.size() && (strip[j].second - strip[i].second) < minDist; j++)
if(strip[i].first != 0 && strip[j].first != 0)
minDist = min(minDist, dist(strip[i], strip[j]));
}
//returnare rezultat
return minDist;
}
//dupa ce am sortat dupa y avem nevoie sa interclasam partea din stanga cu partea din dreapta
void interclasare(int mid_index, int right_index) {
final_interclasare.resize(right_index + 1);
int i = 0, j = mid_index + 1;
int k = 0;
while (i <= mid_index && j <= right_index) {
if (Vy[i] < Vy[j]) {
final_interclasare[k++] = Vy[i];
i++;
}
else {
final_interclasare[k++] = Vy[j];
j++;
}
}
while (i <= mid_index) {
final_interclasare[k++] = Vy[i];
i++;
}
while (j <= right_index) {
final_interclasare[k++] = Vy[j];
j++;
}
}
//functie in urma careia aflam cele maxim 8 puncte de comparat
double minDist(int left, int right) {
if (right - left + 1 <= 3) { //daca avem doar 3 elemente le comparam cu bruteForce
for (int i = left; i <= right; i++)
Vy[i] = V[i];
sort_BruteForce(left, right);
return bruteForce(left, right);
}
int mid = left + (right - left) / 2;
point midPoint = V[mid];
double leftDist = minDist(left, mid); //punctele din stanga
double rightDist = minDist(mid + 1, right); //punctele din dreapta
double localMinDist = min(leftDist, rightDist); //distanta cea mai mica
//interclasare cu i de la left si j de la mid + 1
interclasare(mid, right);
return min(localMinDist, closestOverlapping(final_interclasare, localMinDist)); //aici comparam cele maxim 8 puncte din solutia finala
}
int main()
{
ifstream fin("cmap.in");
fin >> N;
for (int i = 0; i < N; i++) { //citire din fisier
point p;
fin >> p.first;
fin >> p.second;
V[i] = p;
}
//resize la N
V.resize(N);
Vy.resize(N);
sort(V.begin(), V.end()); //sortare dupa coordonata x
ofstream fout("cmap.out"); //afisare in fisier
fout << fixed << setprecision(PRECISION) << minDist(0, N - 1);
fin.close();
fout.close();
}