Pagini recente » Cod sursa (job #1180632) | Cod sursa (job #966262) | Atasamentele paginii Clasament cei_mai_mari_olimpicari_runda_4 | Cod sursa (job #1092741) | Cod sursa (job #2070880)
#include <iostream>
#include<vector>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<limits>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
int x,y;
};
bool compara(punct i, punct j)
{
return (i.x<j.x);
}
bool comparaY(punct i, punct j)
{
return (i.y<j.y);
}
long double distanta(punct i, punct j)
{
long double d = sqrt((i.x - j.x)*(i.x - j.x)+(i.y - j.y)*(i.y - j.y));
return d;
}
long double distMinVector (int stg, int dr, vector<punct> v)//(dr-stg+1)^2 complexitatea
{
//atinge dreapta!
long double dmin = distanta(v[stg],v[stg+1]);
long double d;
for(int i=stg; i<dr; i++)
{
for(int j=i+1; j<=dr; j++)
{
d = distanta(v[i],v[j]);
if(dmin > d)
dmin = d;
}
}
// cout<<dmin<<endl;
return dmin;
}
void citire(int &n, vector<punct> &v)
{
punct z;
f>>n;
for(int i=0; i<n; i++)
{
f>>z.x>>z.y;
v.push_back(z);
}
}
long double divide(int n,int S, int D, vector<punct> X)
{
punct p1,p2;
if(n<=3)
{
return distMinVector(0,n-1,X);
}
int mij = n/2;
//stapaneste
long double distStg = divide(mij,0,mij-1,X);//nu contine si mijlocul
long double distDr = divide(n-mij,mij,n-1,X);//contine si mijlocul
//stop stapaneste
//Combina/Cucereste
long double dist = min(distStg,distDr);
vector<punct> sirY;//contine toate punctele ce sunt la o distanta de cel mult dist de dreapta din mijloc si se sorteaza dupa Y
int j=0;
for(int i=S; i<=D; i++) //adaug punctele cu distanta cel mult dist
{
if(abs(X[i].x-X[mij].x)<=dist)
{
sirY.push_back(X[i]);
j++;
}
}
//sortez
sort(sirY.begin(),sirY.end(),comparaY);
//pt fiecare punct p din sirY cauta in primele 7 puncte care dintre ele sunt la distanta de cel mult dist fata de p
long double dmin2=dist;//maximul
for(int i=0; i<(int)sirY.size(); i++)
{
long double d1;
int stop = min((int)sirY.size()-i-1,i+7); //sa vad daca sunt 7 puncte
//cout<<endl;
for(int k=i+1; k<=stop; k++)
{
//cout<<"1 ";
//d1 = distanta(X[i],X[k]);
if((sirY[k].y-sirY[i].y)<=dist)
{
d1 = distanta(sirY[i],sirY[k]);
if(dmin2>d1)
{
dmin2=d1;
p1 = sirY[i];
p2=sirY[k];
}
}
}
// cout<<endl;
}
return min(dist,dmin2);
}
void lucreaza(int n, vector<punct> &v)
{
//ordonez v dupa x
sort(v.begin(),v.end(),compara);
// cout<<"Vectorul ordonat dupa x: \n";
/* for(int i=0; i<n; i++)
{
cout<<v[i].x<<" "<<v[i].y<<endl;
}*/
//cout<<"Distanta minima este: "<< setprecision (9)<<divide(n,0,n-1,v);
g<< setprecision (9)<<divide(n,0,n-1,v);
}
int main()
{
int n;//nr de puncte
vector<punct> v;
citire(n,v);
lucreaza(n,v);
return 0;
}