Pagini recente » Cod sursa (job #2389245) | Cod sursa (job #1473494) | Cod sursa (job #2657412) | Cod sursa (job #2153308) | Cod sursa (job #2272417)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#define Nmax 1005
#define MINF 10000000
#include <utility>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
double distance(pair<int, int> p1, pair<int, int> p2)
{
return 1.0*(sqrt((p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second)));
}
int n;
pair<int, int> v[Nmax];
double Calcul(int ps, int pf, vector <pair<int, int>> Y)
{
if (pf - ps + 1 <= 3)
{
double mini = MINF;
for (int i = ps; i<pf; i++)
for (int j = i + 1; j <= pf; j++)
if (distance(v[i], v[j])<mini) mini = distance(v[i], v[j]);
return mini;
}
int x_dr;//ecuatia dreptei de despartire
int mij;
mij = (pf - ps + 1) / 2;
x_dr = v[(pf - ps + 1) / 2].first;
vector <pair<int, int>> dy1;//punct punctele sortate dupa y, situate in stanga dreptei de despartire
vector <pair<int, int>> dy2;
for (int i = ps; i <= pf; i++)
if (v[i].first <= x_dr) dy1.push_back(v[i]);
else dy2.push_back(v[i]);
double min1 = Calcul(ps, mij, dy1);
double min2 = Calcul(mij + 1, pf, dy2);
min2 = min(min2, min1);
double min3 = MINF;
vector <pair<int, int>>YIntersectat;
for (pair<int, int> aux : Y)
if (abs(aux.first - x_dr) <= min2) YIntersectat.push_back(aux);
for (int i = 0; i<YIntersectat.size(); i++)
for (int j = i + 1; j <= i + 7; j++)
if(j<YIntersectat.size())
if (distance(YIntersectat[i], YIntersectat[j])<min3)
min3 = distance(YIntersectat[i], YIntersectat[j]);
return (min(min3, min2));
}
bool cmp(pair<int, int>p1, pair<int, int>p2)
{
return (p1.first < p2.first);
}
int main()
{
vector <pair<int, int>> Y;
fin >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
fin >> x >> y;
pair<int, int> aux;
aux.first = x;
aux.second = y;
v[i] = aux;
Y.push_back(aux);
}
//fout<<Y[56].first;
sort(v + 1, v + n + 1, cmp);
fout << Calcul(1, n, Y);
return 0;
}