Pagini recente » Cod sursa (job #2214340) | Istoria paginii utilizator/opreamihay | Istoria paginii utilizator/anahita | Monitorul de evaluare | Cod sursa (job #2070143)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
struct Point{
long long x;
long long y;
const Point& operator=(const Point& P)
{
x = P.x;
y = P.y;
return P;
}
int operator==(const Point& P)
{
return (x == P.x && y == P.y);
}
};
long long returnDist(Point& P1, Point& P2)
{
return (long long) (P2.x - P1.x) * (long long) (P2.x - P1.x) +
(long long) (P2.y - P1.y) * (long long) (P2.y - P1.y);
}
int compByX(const Point& P1,const Point& P2)
{
return P1.x < P2.x;
}
int compByY(const Point& P1,const Point& P2)
{
return P1.y < P2.y;
}
vector<Point> Points;
vector<Point> PointsOY;
Point X1, X2;
long long divideClosPoints(long long left, long long right)
{
if(right - left == 1)
{
if(Points[left].y > Points[right].y )
{
Point X = PointsOY[left];
PointsOY[left] = PointsOY[right];
PointsOY[right] = X;
}
return returnDist(Points[left], Points[right]);
}
if(right - left == 2)
{
Point X;
if(PointsOY[left].y > PointsOY[left+1].y &&
PointsOY[left].y > PointsOY[right].y &&
PointsOY[left+1].y > PointsOY[right].y )
{
X = PointsOY[left];
PointsOY[left] = PointsOY[right];
PointsOY[right] = X;
}
if(PointsOY[left].y > PointsOY[left + 1].y &&
PointsOY[left].y > PointsOY[right].y &&
PointsOY[left + 1].y < PointsOY[right].y)
{
X = PointsOY[left];
PointsOY[left] = PointsOY[left+1];
PointsOY[left+1] = X;
X = PointsOY[right];
PointsOY[right] = PointsOY[left + 1];
PointsOY[left+1] = X;
}
if(PointsOY[left].y < PointsOY[left+1].y &&
PointsOY[left].y > PointsOY[right].y )
{
X = PointsOY[right];
PointsOY[right] = PointsOY[left];
PointsOY[left] = X;
X = PointsOY[left+1];
PointsOY[left+1] = PointsOY[right];
PointsOY[right] = X;
}
if(PointsOY[left].y < PointsOY[left+1].y &&
PointsOY[left].y < PointsOY[right].y &&
PointsOY[left+1].y > PointsOY[right].y)
{
X = PointsOY[left + 1];
PointsOY[left+1] = PointsOY[right];
PointsOY[right] = X;
}
return min(returnDist(Points[left], Points[left+1]),
min(returnDist(Points[left+1], Points[right]),
returnDist(Points[left], Points[right])));
}
long long middle = (left + right) / 2;
long long dLeft = divideClosPoints(left, middle);
long long dRight = divideClosPoints(middle + 1, right);
long long d = min(dLeft, dRight);
long i, j;
vector<Point> verticalSec;
vector<Point> sol;
i = left;
j = middle + 1;
while(i <= middle && j <= right)
{
if(PointsOY[i].y < PointsOY[j].y)
{
sol.push_back(PointsOY[i]);
i++;
}
else
{
sol.push_back(PointsOY[j]);
j++;
}
}
while(i <= middle)
{
sol.push_back(PointsOY[i]);
i++;
}
while(j <= right)
{
sol.push_back(PointsOY[j]);
j++;
}
j = 0;
for(i = left; i <= right; i++)
{
PointsOY[i] = sol[j++];
}
for(i = left ; i <= right; i++)
{
if(abs(PointsOY[i].x - Points[middle].x) <= d)
{
verticalSec.push_back(PointsOY[i]);
}
}
long long sizeV = verticalSec.size();
for(i = 0; i < sizeV ; i++)
for(j = i + 1; j <= i + 7 && j < sizeV ; j++)
{
d = min(d, returnDist(verticalSec[i],verticalSec[j]));
}
return d;
}
int main()
{
ifstream fileRead("cmap.in");
ofstream fileWrite("cmap.out");
long long nrPoints, i;
Point P;
fileRead >> nrPoints;
for(i = 0 ; i < nrPoints; i++)
{
fileRead >> P.x >> P.y;
Points.push_back(P);
PointsOY.push_back(P);
}
long long dist = returnDist(Points[0],Points[1]);
sort(Points.begin(),Points.end(),compByX);
//long long res = divideClosPoints(0,nrPoints - 1);
//cout << " res = " << res << '\n';
fileWrite << fixed << setprecision(6) << sqrt(divideClosPoints(0,nrPoints - 1));
fileRead.close();
fileWrite.close();
}