Pagini recente » Cod sursa (job #273819) | Borderou de evaluare (job #1036155) | Cod sursa (job #1823566) | Cod sursa (job #1837450) | Cod sursa (job #1042051)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define NMax 100010
#define INF 8000000000000000000LL
#define limit 1000000
#define Next ++position == limit?f.read(buffer, limit), position = 0:0
using namespace std;
ifstream f ("cmap.in");
int n;
int position;
char buffer[limit];
pair<int, int> X[NMax], Y[NMax], aux[NMax];
inline void Read(int &x)
{
for (; buffer[position] < '0' || buffer[position] > '9'; Next);
for (x = 0; '0' <= buffer[position] && buffer[position] <= '9'; x = x*10 + buffer[position] - '0', Next);
}
void Read()
{
Read(n);
for (int i = 0; i<n; ++i)
Read(X[i].first), Read(X[i].second);
sort(X, X+n);
for (int i = 0; i<n; ++i)
Y[i] = make_pair(X[i].second, X[i].first);
}
inline long long sqr(const int x)
{
return 1LL*x*x;
}
inline long long Dist(const pair<int, int> A, const pair<int, int> B)
{
return sqr(A.first - B.first) + sqr(A.second - B.second);
}
inline long long cmap(const int st, const int dr)
{
/// returneaza distanta celor mai apropiate 2 puncte din multimea [st, dr) din vectorul X sortat dupa x
/*if (dr - st <= 1) <=> (dr <= st + 1) <=> (st >= dr - 1)*/
/// daca am doar un punct in setul meu sau daca st a depasit dr atunci returnez infinit
if (st >= dr - 1)
return INF;
/// daca am doua puncte atunci le sortez dupa y in vectorul Y si returnez distanta dintre ele
if (dr - st == 2)
{
sort (Y+st, Y+dr);
return Dist(X[st], X[st+1]);
}
int i, j, mij;
long long distance;
mij = (st+dr)>>1;
distance = min (cmap(st, mij), cmap(mij, dr));
///interclasam in vectorul aux vectorii Ys si Yd corespunzatori celor 2 impartiri ale planului efectuate
merge(Y+st, Y+mij, Y+mij, Y+dr, aux);
/// copiem la pozitia st in vectorul Y pe aux care reprezinta interclasarea lui Ys si Yd
copy(aux, aux+dr-st, Y+st);
/// selectam fasia de latime 2*distance in jurul dreptei alese
int len = 0;
for (i=st; i<dr; ++i)
if (abs(Y[i].second - X[mij].first) <= distance)
aux[++len] = Y[i];
/// avand un dreptunghi de dimensiuni distance * (2distance) despartit in 2 patrate de dimensiuni
/// distance*distance pot sa aleg in fiecare patrat maxim 4 puncte care sa fie la distanta cel putin
/// distance si anume in cele 4 colturi deci in total 8 puncte (in cazul in care pe dreapta care imparte
/// planul in cele 2 puncte din colturi ar fi de fapt 4.. care sa coincida etc..)
/// cum eu a aleg un punct i -> mai raman 7 de vazut
for (i=1; i<=len; ++i)
for (j=i+1; j<=len && j-i < 8; ++j)
distance = min(distance, Dist(aux[i], aux[j]));
return distance;
}
void Write()
{
FILE *g = fopen("cmap.out", "w");
fprintf(g, "%.6lf\n", sqrt(1.0*(cmap(0, n))));
fclose(g);
}
int main()
{
Read();
Write();
return 0;
}