Pagini recente » Cod sursa (job #1415329) | Cod sursa (job #1684373) | Cod sursa (job #2385129) | Cod sursa (job #1577181) | Cod sursa (job #1047829)
#include<iostream>
#include<fstream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
struct punct{
double x;
double y;
};
long long distanta(punct x, punct y){
return sqrt(pow(x.x - y.x, 2) + pow(x.y - y.y, 2));
}
int cmp(const void *x, const void *y){
punct x1 = (*((punct*)x));
punct y1 = (*((punct*)y));
if (x1.x > y1.x){
return 1;
}
else{
if (x1.x == y1.x){
if (x1.y > y1.y){
return 1;
}
return -1;
}
}
return -1;
}
punct puncte[100000];
vector<punct> Vpuncte;
bool sorteazaDupaY(const punct &a, const punct &b)
{
return (a.y < b.y);
}
bool sorteazaDupaX(const punct &a, const punct &b)
{
return (a.x < b.x);
}
long long rezolva(int left, int right)
{
long long d;
if (right - left <= 2)
{
d = 10000000000000;
for (int i = left; i < right; i++)
{
for (int j = i + 1; j <= right; j++)
{
d = min(distanta(puncte[i], puncte[j]), d);
}
}
sort(puncte + left, puncte + right + 1, sorteazaDupaY);
return d;
}
else
{
int middle = left + (right - left) / 2;
d = min(rezolva(left, middle), rezolva(middle + 1, right));
int l = left;
int r = middle + 1;
Vpuncte.clear();
while ((l <= middle) && (r <= right))
{
if (sorteazaDupaY(puncte[l], puncte[r]) == true)
{
Vpuncte.push_back(puncte[l]);
l++;
}
else
{
Vpuncte.push_back(puncte[r]);
r++;
}
}
while (l <= middle)
{
Vpuncte.push_back(puncte[l]);
l++;
}
while (r <= right)
{
Vpuncte.push_back(puncte[r]);
r++;
}
for (int i = left, k = 0; i <= right; i++, k++)
{
puncte[i] = Vpuncte[k];
}
for (int i = left; i <= right; i++)
{
for (int j = i + 1; (j <= right) && (j - i < 7); j++)
{
d = min(distanta(puncte[i], puncte[j]), d);
}
}
return d;
}
}
int main(){
ifstream f("cmap.in");
int n = 0; f >> n;
for (int i = 0; i < n; i++){
punct p;
f >> p.x >> p.y;
puncte[i] = p;
}
sort(puncte, puncte + n, sorteazaDupaX);
/*double min = pow(10, 9);
for (int i = 0; i < n-1; i++){
for (int j = i + 1; j < n; j++){
double dist = distanta(puncte[i], puncte[j]);
if ( dist< min){
min = dist;
break;
}
}
}*/
ofstream o("cmap.out");
long long dist = rezolva(0, n - 1);
o <<fixed<< dist << '\n';
return 0;
}