Pagini recente » Cod sursa (job #2164503) | Cod sursa (job #2942130) | Cod sursa (job #1853488) | Cod sursa (job #1100125) | Cod sursa (job #2089054)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define x first
#define y second
using namespace std;
pair<int,int>pct[100005];
pair<int,int>pct2[100005];
int n,k,d;
double s;
double minim(int s,int n)
{
double m=99999999;
for(int i=s;i<n-1;i++)
for(int j=i+1;j<n;j++)
{
double k=0;
k=sqrt(1.0*(pct[j].x-pct[i].x)*(pct[j].x-pct[i].x)+(pct[j].y-pct[i].y)*(pct[j].y-pct[i].y));
m=min(m,k);
}
return m;
}
void sol()
{
k=0;
for(int i=n/2;i>=0&&k<=4;i--)
{
if(pct[i].x>=d-s)
{pct2[k]={pct[i].x,pct[i].y};k++;}
else break;
}
int l=k+4;
for(int i=n/2+1;i<n&&k<=l;i++)
{
if(pct[i].x<=d+s)
{pct2[k]={pct[i].x,pct[i].y};k++;}
else break;
}
}
int main()
{
ifstream f ("cmap.in");
ofstream g ("cmap.out");
f>>n;
for(int i=0;i<n;i++)
{
int a,b;
f>>a>>b;
pct[i]={a,b};
}
sort(pct,pct+n);
double ss=minim(0,n/2);
double sd=minim(n/2,n-1);
d=(pct[n/2].x+pct[n/2+1].x)/2;
s=min(ss,sd);
sol();
sort(pct2,pct2+k);
for(int i=0;i<k-1;i++)
for(int j=i+1;j<k;j++)
{
double c;
c=sqrt((pct2[j].x-pct2[i].x)*(pct2[j].x-pct2[i].x)+(pct2[j].y-pct2[i].y)*(pct2[j].y-pct2[i].y));
s=min(s,c);
}
g<<setprecision(6)<<fixed<<s;
return 0;
}