Pagini recente » Cod sursa (job #1305539) | Cod sursa (job #871260) | Cod sursa (job #437645) | Cod sursa (job #184034) | Cod sursa (job #1736403)
#include<cstdio>
#include<cmath>
#define MAXN 50010
#define EPS 1e-14
using namespace std;
struct Point{
double x,y;
};
Point v[MAXN];
int n;
double Distance(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Compute(Point sample){
int i;
double answer=0.0;
for(i=1;i<=n;i++)
answer+=Distance(sample,v[i]);
return answer;
}
void HillClimbing(){
int i;
double current,step,d1,d2,d3,d4,best;
Point answer={0.0,0.0},try1,try2,try3,try4,next;
for(i=1;i<=n;i++){
answer.x+=v[i].x;
answer.y+=v[i].y;
}
answer.x/=n;
answer.y/=n;
current=Compute(answer);
step=100;
for(i=1;i<=35;i++){
try1={answer.x,answer.y-step};
try2={answer.x-step,answer.y};
try3={answer.x,answer.y+step};
try4={answer.x+step,answer.y};
d1=Compute(try1);
d2=Compute(try2);
d3=Compute(try3);
d4=Compute(try4);
best=d1;
next=try1;
if(best-d2>=EPS){
best=d2;
next=try2;
}
if(best-d3>=EPS){
best=d3;
next=try3;
}
if(best-d4>=EPS){
best=d4;
next=try4;
}
if(current-best>=EPS){
answer=next;
current=best;
}
else
step/=2;
}
printf("%.4f %.4f",answer.x,answer.y);
}
int main(){
freopen("adapost2.in","r",stdin);
freopen("adapost2.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
HillClimbing();
return 0;
}