Pagini recente » Istoria paginii runda/rep/clasament | Cod sursa (job #1298992) | Agm 2018 Runda 1 | Istoria paginii runda/problemebarajgimnaziu/clasament | Cod sursa (job #3037902)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
class InParser {
vector<char> str;
int ptr;
ifstream fin;
char getChar() {
if (ptr == int(str.size())) {
fin.read(str.data(), str.size());
ptr = 0;
}
return str[ptr++];
}
template<class T>
T getInt() {
char chr = getChar();
while (!isdigit(chr) && chr != '-')
chr = getChar();
int sgn = +1;
if (chr == '-') {
sgn = -1;
chr = getChar();
}
T num = 0;
while (isdigit(chr)) {
num = num * 10 + chr - '0';
chr = getChar();
}
return sgn * num;
}
public:
InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
~InParser() { fin.close(); }
template<class T>
friend InParser& operator>>(InParser& in, T& num) {
num = in.getInt<T>();
return in;
}
};
InParser fin("cmap.in");
ofstream fout("cmap.out");
struct Pct{
double i, j;
}x[100001];
bool C(Pct a, Pct b)
{if(a.i<b.i || (a.i==b.i && a.j<b.j))return 1;
return 0;
}
double Dist(double x1, double y1, double x2, double y2)
{double a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
return a;
}
double DQ(int st, int dr)
{if(dr-st+1<=3)
{double mini=1e9;
for(int i=st;i<dr;i++)
for(int j=i+1;j<=dr;j++)
mini=min(mini, Dist(x[i].i, x[i].j, x[j].i, x[j].j));
return mini;
}
else
{int mij=(st+dr)/2;
double mini=min(DQ(st, mij), DQ(mij+1, dr));
vector<Pct> y;
for(int i=st;i<=dr;i++)
if(abs(x[i].i-x[mij].i)<=mini)y.push_back(x[i]);
for(int i=0;i<y.size()-1;i++)
for(int j=i+1;j<y.size();j++)
mini=min(mini, Dist(y[i].i, y[i].j, y[j].i, y[j].j));
return mini;
}
}
int main()
{ int n;
fin>>n;
for(int i=1;i<=n;i++)
fin>>x[i].i>>x[i].j;
sort(x+1, x+1+n, C);
DQ(1, n);
fout<<fixed<<setprecision(6)<<DQ(1, n);
return 0;
}