Cod sursa(job #1869752)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 6 februarie 2017 09:48:48
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <cmath>

#define MAXN 50000

int n;

struct myc{
    double x, y;
}v[MAXN+1];

inline double calc(double x, double y){
    double ans=0;
    for(int i=1; i<=n; i++)
        ans+=sqrt((x-v[i].x)*(x-v[i].x)+(y-v[i].y)*(y-v[i].y));
    return ans;
}

int main(){
    FILE *fin, *fout;
    fin=fopen("adapost2.in", "r");
    fout=fopen("adapost2.out", "w");

    fscanf(fin, "%d", &n);

    double gx=0, gy=0;
    for(int i=1; i<=n; i++){
        fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
        gx+=v[i].x;
        gy+=v[i].y;
    }
    gx/=n;
    gy/=n;

    double pas=1<<9;
    while(pas>0.001){
        double s=calc(gx, gy), dr=calc(gx+pas, gy), st=calc(gx-pas, gy), sus=calc(gx, gy+pas), jos=calc(gx, gy-pas);
        if((jos<s)&&(st<s)){
            double a=s-st, b=s-jos;
            gx-=a/(a+b)*pas;
            gy-=b/(a+b)*pas;
        }else if((st<s)&&(sus<s)){
            double a=s-st, b=s-sus;
            gx-=a/(a+b)*pas;
            gy+=b/(a+b)*pas;
        }else if((sus<s)&&(dr<s)){
            double a=s-dr, b=s-sus;
            gx+=a/(a+b)*pas;
            gy+=b/(a+b)*pas;
        }else if((dr<s)&&(jos<s)){
            double a=s-dr, b=s-jos;
            gx+=a/(a+b)*pas;
            gy-=b/(a+b)*pas;
        }else if(st<s) gx-=pas;
        else if(sus<s) gy+=pas;
        else if(dr<s) gx+=pas;
        else if(jos<s) gy-=pas;
        else pas/=2;
    }

    fprintf(fout, "%.12f %.12f\n", gx, gy);

    fclose(fin);
    fclose(fout);
    return 0;
}