Pagini recente » Cod sursa (job #623756) | Cod sursa (job #1945400) | Cod sursa (job #344164) | Cod sursa (job #507020) | Cod sursa (job #1820393)
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <math.h>
#define i64 unsigned long long
#define INF 2000000000
#define MAXN 100010
#define BUFF_SIZE 1048576
using namespace std;
class punct{
public:
i64 x;
i64 y;
bool operator <(const punct p2) const
{
return x < p2.x;
}
};
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch()
{
++sp;
if (sp == BUFF_SIZE) {
sp = 0;
fread(buff, 1, BUFF_SIZE, fin);
}
return buff[sp];
}
public:
InParser(const char* nume)
{
fin = fopen(nume, "r");
buff = new char[BUFF_SIZE]();
sp = BUFF_SIZE-1;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (unsigned long long &n)
{
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
i64 compareY(const punct a, const punct b)
{
return (a.y < b.y);
}
punct X[100005], Y[100005];
int N;
i64 last;
i64 pldist(punct p1, punct p2)
{
return /*sqrt*/( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y) );
}
i64 brutu(punct p[], int n)
{
i64 minim = 4e18;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (pldist(p[i], p[j]) < minim)
minim = pldist(p[i], p[j]);
return minim;
}
i64 minfasie(punct fasie[], int sz, i64 dist)
{
i64 minim = dist;
// sort(fasie, fasie+sz, compareY);
for (int i = 0; i < sz; ++i)
for (int j = i+1; j < sz && (fasie[j].y - fasie[i].y) < minim; ++j)
if (pldist(fasie[i],fasie[j]) < minim)
minim = pldist(fasie[i], fasie[j]);
return minim;
}
i64 div_and_q(int st, int dre, punct x[], punct y[])
{
if(dre-st<3)
return brutu(x, dre-st);
int mid = (st+dre)/2;
punct mijloc = x[mid]; //puncte prin care ducem o || la Oy
//punct yl[dre-st+1]; // y stanga
//punct yr[dre-st+1]; // y dreapta
int li=0, ri=0;
/*for (int i = 0; i < dre-st; i++)
{
if (y[i].x <= mijloc.x)
{
yl[li] = y[i];
++li;
}
else
{
yr[ri] = y[i];
++ri;
}
}*/
i64 dl = div_and_q(st, mid, x, y);
i64 dr = div_and_q(mid, dre, x, y);
i64 dist = min(dl, dr);
//cout<<dist<<"\n";
sort(y + st, y + dre, compareY);
punct fasie [dre-st];
int j = 0;
for (int i = st; i < dre; ++i)
if (abs(y[i].x - mijloc.x) < dist)
{
fasie[j] = y[i];
++j;
}
return min(dist, minfasie(fasie, j, dist));
}
int main()
{
InParser in("cmap.in");
//ifstream in ("cmap.in");
ofstream out ("cmap.out");
int i;
in>>N;
for(i=0;i<N;++i)
in>>X[i].x>>X[i].y;
sort(X, X+N);
for(i=0;i<N;++i)
Y[i]=X[i];
out<<fixed<<setprecision(6)<<sqrt(div_and_q(0, N, X, Y));
//in.close();
out.close();
return 0;
}