Pagini recente » Cod sursa (job #1996463) | Cod sursa (job #967175) | Clasament cerculdeinfo-lectia18-grafuri2 | Cod sursa (job #500554) | Cod sursa (job #1282517)
// FMI - Grupa 135 - Semigrupa 2 - Hareza Andrei
// Include
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
// Definitii
#define ll long long
// Clase
class point_t
{
int x, y;
public:
point_t()
{
x = y = 0;
}
bool operator<(point_t p) const
{
return x == p.x? y < p.y : x < p.x;
}
bool operator<<(point_t p) const
{
return y == p.y? x < p.x : y < p.y;
}
ll distTo(point_t p)
{
return 1LL*(x-p.x) * (x-p.x) + 1LL*(y-p.y) * (y-p.y);
}
int xDist(point_t p)
{
int dist = x -p.x;
return dist<0? -dist : dist;
}
friend istream &operator>>(istream &file, point_t &p);
};
istream &operator>>(istream &file, point_t &p)
{
file >> p.x >> p.y;
return file;
}
// Constante
const int sz = 100001;
const ll oo = (1LL<<63)-1LL;
// Functii
ll findDist(int left, int right);
// Variabile
ifstream in("cmap.in");
ofstream out("cmap.out");
int num;
point_t points[sz], temp[sz];
// Main
int main()
{
in >> num;
for(int i=1 ; i<=num ; ++i)
in >> points[i];
sort(points+1, points+num+1);
out << fixed << setprecision(6) << sqrt(findDist(1, num));
in.close();
out.close();
return 0;
}
ll findDist(int left, int right)
{
if(right - left < 2)
{
if(right == left)
return oo;
else
{
if(points[right] << points[left])
swap(points[left], points[right]);
return points[left].distTo(points[right]);
}
}
int mid = (left + right) / 2;
point_t midPoint = points[mid];
ll dist = min(findDist(left, mid), findDist(mid+1, right));
int left1 = left, right1 = mid;
int left2 = mid+1, right2 = right;
int current = left-1;
while(left1 <= right1 && left2 <= right2)
{
if(points[left1] << points[left2])
temp[++current] = points[left1++];
else
temp[++current] = points[left2++];
}
while(left1 <= right1)
temp[++current] = points[left1++];
while(left2 <= right2)
temp[++current] = points[left2++];
for(int i=left ; i<=right ; ++i)
points[i] = temp[i];
int tempSize = 0;
for(int i=left ; i<=right ; ++i)
if(midPoint.xDist(points[i]) < dist)
temp[++tempSize] = points[i];
for(int i=1 ; i<=tempSize ; ++i)
for(int j=i+1 ; j<=tempSize && temp[i].distTo(temp[j]) < dist; ++j)
dist = temp[i].distTo(temp[j]);
return dist;
}