Cod sursa(job #1736403)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 1 august 2016 17:46:28
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#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;
}