Pagini recente » Cod sursa (job #3232236) | Cod sursa (job #1752834) | Cod sursa (job #2735108) | Cod sursa (job #2222709) | Cod sursa (job #1542166)
#include<fstream>
#include<iostream>
#include<cmath>
#include<limits>
using namespace std;
class Punct
{
public:
long long x, y;
Punct(long long x, long long y)
{
this->x = x;
this->y = y;
}
Punct()
{
x = y = 0;
}
long long distance(Punct p)
{
return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);
}
} *P;
long long getMin(int start, int end, Punct ySorted[])
{
long long minSt, minDr, minD;
if(end - start <= 2)
{
minD = P[start].distance(P[start+1]);
for(int i = start; i < end; i++)
for(int j = i+1; j<= end; j++)
if(P[i].distance(P[j]) < minD)
minD = P[i].distance(P[j]);
for(int i = start; i<= end; i++)
ySorted[i] = P[i];
for(int i = start; i < end; i++)
{
int min = i;
Punct aux;
for(int j = i+1; j <= end; j++)
if(ySorted[min].y > ySorted[j].y)
min = j;
if(min != i)
{
aux = ySorted[i];
ySorted[i] = ySorted[min];
ySorted[min] = aux;
}
}
return minD;
}
minSt = getMin(start, (start + end)/2, ySorted);
minDr = getMin((start + end)/2+1, end, ySorted);
minD = minSt < minDr ? minSt : minDr;
int a = start, b = (start+end)/2+1, ntmp = 0;
Punct *tmp = new Punct[end-start+1];
while(a <= (start+end)/2 && b <= end)
if(ySorted[a].y < ySorted[b].y)
tmp[ntmp++] = ySorted[a++];
else
tmp[ntmp++] = ySorted[b++];
while(a <= (start+end)/2)
tmp[ntmp++] = ySorted[a++];
while(b <= end)
tmp[ntmp++] = ySorted[b++];
for(int i = 0; i < ntmp; i++)
ySorted[i+start] = tmp[i];
Punct *db = new Punct[ntmp];
int ndb = 0;
for(int i = start; i <= end; i++)
if(abs(ySorted[i].x - P[(start+end)/2].x) <= minD)
db[ndb++] = ySorted[i];
for(int i = 0; i < ndb; i++)
for(int j = i+1; j < ndb && j <= i + 7; j++)
if(db[i].distance(db[j]) < minD)
minD = db[i].distance(db[j]);
delete db;
delete tmp;
return minD;
}
int main()
{
int n;
long a, b;
Punct *s;
fstream in("cmap.in", ios::in), out("cmap.out", ios::out);
in>>n;
P = new Punct[n];
s = new Punct[n];
for(int i = 0; i < n; i++)
{
in>>a;
in>>b;
P[i] = Punct(a,b);
}
in.close();
out<<fixed<<sqrt(getMin(0, n-1, s));
out.close();
delete P;
delete s;
return 0;
}