Pagini recente » Cod sursa (job #1756036) | Cod sursa (job #1730893) | Cod sursa (job #1796001) | Cod sursa (job #1473333) | Cod sursa (job #329425)
Cod sursa(job #329425)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define MAX 1000000
#define DIM 50005
struct punct {int x,y;} a[DIM],sol;
int dx[4]={1,0,-1, 0};
int dy[4]={0,1, 0,-1};
double min_tot;
int n;
void read ()
{
double x,y;
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
{
scanf ("%lf%lf",&x,&y);
x*=1000;
y*=1000;
a[i].x=(int)x;
a[i].y=(int)y;
}
}
double dist (int x,int y)
{
double sum=0;
int i;
for (i=1; i<=n; ++i)
sum+=sqrt ((x-a[i].x)*(x-a[i].x)+(y-a[i].y)*(y-a[i].y));
return sum;
}
void solve ()
{
double d[5],min;
int plm,i,ind;
punct t;
for (t.x=rand ()%MAX+1, t.y=rand ()%MAX+1, min_tot=dist (t.x,t.y), plm=MAX; plm; )
{
for (i=0; i<4; ++i)
d[i]=dist (t.x+dx[i]*plm,t.y+dy[i]*plm);
min=d[0];
ind=0;
for (i=1; i<4; ++i)
if (d[i]<min)
{
min=d[i];
ind=i;
}
if (min<min_tot)
{
t.x+=dx[ind]*plm;
t.y+=dy[ind]*plm;
min_tot=min;
sol=t;
}
else
plm>>=1;
}
printf ("%.4f %.4f",(float)sol.x/1000,(float)sol.y/1000);
}
int main ()
{
freopen ("adapost2.in","r",stdin);
freopen ("adapost2.out","w",stdout);
srand (time (0));
read ();
solve ();
return 0;
}