Pagini recente » Cod sursa (job #1736207) | Cod sursa (job #1787091) | Cod sursa (job #2519818) | Cod sursa (job #673344) | Cod sursa (job #1075129)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f ("cmap.in");
ofstream g ("cmap.out");
int n, px, py, i, j, b, e, c, p, m;
int x[100000], y[100000];
long double d1, d2, d3, s1, s2, ss, mn;
double ddcmap(int s, int d)
{
b=-1000000000;
p=0;
for(i=0; i<=n; i++)
{
p++;
if(b==-1000000000 && x[i]>=s)
b=i;
if(x[i]<=d)
e=i;
else
break;
}
if(p<=3)
{
if(p==2)
return ( sqrt( ((double)x[b]-(double)x[e])*((double)x[b]-(double)x[e]) + ((double)y[b]-(double)y[e])*((double)y[b]-(double)y[e]) ) );
d1 = sqrt( ((double)x[b]-(double)x[e])*((double)x[b]-(double)x[e]) + ((double)y[b]-(double)y[e])*((double)y[b]-(double)y[e]) );
d2 = sqrt( ((double)x[b+1]-(double)x[e])*((double)x[b+1]-(double)x[e]) + ((double)y[b+1]-(double)y[e])*((double)y[b+1]-(double)y[e]) );
d3 = sqrt( ((double)x[b]-(double)x[e-1])*((double)x[b]-(double)x[e-1]) + ((double)y[b]-(double)y[e-1])*((double)y[b]-(double)y[e-1]) );
if(d1 >= d2 && d1 >= d3)
return d1;
if(d2 >= d1 && d2 >= d3)
return d2;
return d3;
}
m= (b+e)/2;
s1 = ddcmap(b, m);
s2 = ddcmap(m+1, e);
for(i=b; i<=m; i++)
{
if(x[m]-x[i]<=s1)
{
ss=i;
break;
}
}
mn= 10000000000;
for(i=ss; i < ss+8; i++)
for(j=i+1; j<ss+8; j++)
{
d1 = sqrt( ((double)x[i]-(double)x[j])*((double)x[i]-(double)x[j]) + ((double)y[i]-(double)y[j])*((double)y[i]-(double)y[j]) );
if(d<mn)
mn=d1;
}
ss=s1?s2:(s1<s2);
return mn?ss:(mn<ss);
}
int main()
{
f >> n;
for(; c<n; c++)
{
f >> px >> py;
i=0;
while(x[i]<=px && i<c)
i++;
for(j=c; j>i; j--)
{
x[j]=x[j-1];
y[j]=y[j-1];
}
x[i]=px;
y[i]=py;
}
g<<ddcmap(x[0]-2, x[n-1]+2);
return 0;
}