Nu aveti permisiuni pentru a descarca fisierul grader_test9.ok
Cod sursa(job #11853)
Utilizator | Data | 1 februarie 2007 22:31:17 | |
---|---|---|---|
Problema | Adapost 2 | Scor | 26 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.57 kb |
#include <stdio.h>
#include <math.h>
double a[50001],b[50001], v[16];
double dist(double x1,double y1,double x2,double y2)
{
double x=x1-x2,y=y1-y2;
x*=x;y*=y;
return sqrt(x+y);
}
int main()
{
freopen("adapost2.in","r",stdin);
freopen("adapost2.out","w",stdout);
long i,ii,n,e;
double aprox,X=0,Y=0,d=0,best=0;
v[1]=100;
v[2]=10;
v[3]=1;
v[4]=0,1;
v[5]=0,01;
v[6]=0,001;
v[7]=0,0001;
v[8]=0,00001;
scanf("%ld",&n);
for(i=1;i<=n;++i)
{
scanf("%lf %lf",&a[i],&b[i]);
X+=a[i]/n;
Y+=b[i]/n;
}
for(i=1;i<=n;++i)
best+=dist(a[i],b[i],X,Y);
for(int q=1;q<=8;++q)
{
e=1;
for(ii=1;ii<=10 && e;++ii)
{
e=0;
//st
d=0;
for(i=1;i<=n;++i)
d+=dist(a[i],b[i],X-v[q],Y);
if(d<best)
{
X-=v[q];
e=1;
best=d;
}
//dr
d=0;
for(i=1;i<=n;++i)
d+=dist(a[i],b[i],X+v[q],Y);
if(d<best)
{
X+=v[q];
e=1;
best=d;
}
//sus
d=0;
for(i=1;i<=n;++i)
d+=dist(a[i],b[i],X,Y-v[q]);
if(d<best)
{
Y-=v[q];
e=1;
best=d;
}
//jos
d=0;
for(i=1;i<=n;++i)
d+=dist(a[i],b[i],X,Y+v[q]);
if(d<best)
{
Y+=v[q];
e=1;
best=d;
}
}
}
printf("%lf %lf\n", X, Y);
return 0;
}