Nu aveti permisiuni pentru a descarca fisierul grader_test17.ok
Cod sursa(job #12070)
Utilizator | Data | 2 februarie 2007 21:16:35 | |
---|---|---|---|
Problema | Adapost 2 | Scor | 84 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.66 kb |
#include <cstdio>
#define maxn 50001
#include <cmath>
#define next(p) (((p)*10+1)/(double)10)
struct point { double x, y;};
point x[maxn];
double meda=1000, medb=1000, solx, soly;
double smin=0x3f3f3f3f;
double distance(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int n;
double oki(point a)
{
double sum=0;
for(int i=1;i<=n;i++) sum+=distance(a, x[i]);
return sum;
}
void recursion(double mx, double my, double newx, double newy)
{
point m;
m.x=mx+newx;
m.y=my+newy;
int ok=1;
double sum=oki(m);
if(smin-sum>=0.0000001) {ok=0; smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}
m.x=mx-newx;
m.y=my+newy;
sum=oki(m);
if(smin-sum>=0.0000001) { ok=0;smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}
m.x=mx+newx;
m.y=my-newy;
sum=oki(m);
if(smin-sum>=0.0000001) { ok=0; smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}
m.x=mx-newx;
m.y=my-newy;
sum=oki(m);
if(smin-sum>=0.0000001) { ok=0;smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}
if(newx-0.000001>0 && ok) recursion(mx, my, newx/2.0, newy/2.0);
}
int main()
{
int i;
freopen("adapost2.in", "r",stdin);
scanf("%d\n", &n);
for(i=1;i<=n;i++) scanf("%lf %lf\n", &x[i].x, &x[i].y);
//printf("%f\n", x[1].x);
double medx=0, medy=0;
for(i=1;i<=n;i++) medx+=x[i].x, medy+=x[i].y;
medx=medx/(double) n;
medy=medy/(double) n;
freopen("adapost2.out", "w", stdout);
//printf("%lf %lf\n", medx, medy);
point aux;
aux.x=medx;
aux.y=medy;
meda=1000.0;
medb=1000.0;
smin=oki(aux);
//printf("%lf\n", smin);
solx=medx;
soly=medy;
int ok=1;
while(ok)
{
ok=0;
point m;
m.x=medx+meda;
m.y=medy+medb;
double sum=oki(m);
if(smin-sum>=0.0000001) { ok=1; smin=sum;solx=m.x; soly=m.y;}
m.x=medx+meda;
m.y=medy-medb;
//printf("(%lf)\n", sum);
sum=oki(m);
if(smin-sum>=0.0000001) { ok=1; smin=sum; solx=m.x; soly=m.y;}
m.x=medx-meda;
m.y=medy+medb;
//printf("(%lf)\n", sum);
sum=oki(m);
if(smin-sum>=0.0000001) { ok=1; smin=sum; solx=m.x; soly=m.y;}
m.x=medx-meda;
m.y=medy+medb;
//printf("(%lf)\n", sum);
if(smin-sum>=0.0000001) { ok=1; smin=sum; solx=m.x; soly=m.y;}
medx=solx;
medy=soly;
//printf("(%lf)\n", sum);
if(ok==0 && meda-0.0000001 >0) ok=1;
meda=meda/2.0;
medb=medb/2.0;
// printf("%lf %lf\n", meda, medb);
}
recursion(medx, medy, 1000.0, 1000.0);
printf("%.4lf %.4lf\n", solx, soly);
//printf("%lf\n", smin);
point ap;
ap.x=4.1442; ap.y=4.2898;
//printf("%lf\n", oki(ap));
return 0;
}