Pagini recente » Cod sursa (job #2872166) | Cod sursa (job #1026085)
#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
int n;
ifstream in("cmap.in");
struct punct
{
long long x;
long long y;
}v[100010];
bool sortY(punct a,punct b)
{
return (a.y < b.y);
}
bool sortX(punct a, punct b)
{
if(a.x < b.x)
{
return true;
}
if(a.x == b.x)
{
return sortY(a,b);
}
return false;
}
double myDistance(punct a1, punct a2)
{
double d = (double) (a1.x - a2.x) * (a1.x - a2.x) + (a1.y - a2.y) * (a1.y - a2.y) ;
d = sqrt(d);
return d;
}
double firstCase(int left, int right)
{
double d1,d2;
d1 = myDistance(v[left], v[left+1]);
for(int i = left; i < right ; i++ )
{
for(int j = i + 1 ; j<= right; j++)
{
d2 = myDistance(v[i], v[j]);
if(d2 < d1)
{
d1 = d2;
}
}
}
sort(v+left, v+right + 1, sortY);
return d1;
}
double secondCase(int left, int right, int middle, int distance)
{
double d;
vector < punct > vec;
for(int i=left; i<middle; i++)
{
if(myDistance(v[i],v[middle]) < distance)
{
vec.push_back(v[i]);
}
}
for(int i = middle + 1; i<= right; i++)
{
if(myDistance(v[i],v[middle]) < distance)
{
vec.push_back(v[i]);
}
}
sort(vec.begin(), vec.end(), sortY);
vector<punct>::iterator it = vec.begin();
for(int i = 0; it+i != vec.end(); i++)
{
for(int j = i+1; it + j != vec.end();j++)
{
d = myDistance(*(it+i), *(it+j));
if(distance > d)
{
distance = d;
}
}
}
return distance;
}
double devideAndConquer(int left, int right)
{
double d;
if(right - left <= 2)
{
d = firstCase(left, right);
return d;
}
else
{
double s1,s2;
int middle = left + (right - left) / 2;
s1 = devideAndConquer(left, middle);
s2 = devideAndConquer(middle + 1, right);
if(s1>s2)
{
s1 = s2;
}
s2 = secondCase(left, right, middle, s1);
if(s1<s2)
{
s1 = s2;
}
return s1;
}
}
void read()
{
in>>n;
for(int i = 1 ; i<=n; i++)
{
in>>v[i].x>>v[i].y;
}
}
void write(double d)
{
FILE*g = fopen("cmap.out","w");
fprintf(g, "%.6lf\n", d);
}
int main()
{
read();
sort(v+1,v+n+1, sortX);
double d = devideAndConquer(1,n);
write(d);
}