Cod sursa(job #1082982)

Utilizator WyvernFMI Stanescu Leonard Wyvern Data 15 ianuarie 2014 14:43:49
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.04 kb
#include <fstream>
#include <math.h>
using namespace std;
ifstream fi("adapost2.in");
ofstream fo("adapost2.out");
double x[50001],y[50001],xg,yg,s1,c,q;
int n;
double s2(double xg, double yg) {
    double s=0;
    for(int i=1;i<=n;i++)
        s+=sqrt((x[i]-xg)*(x[i]-xg)+(y[i]-yg)*(y[i]-yg));
    return s;
}
int main() {
    fi>>n;
    for(int i=1;i<=n;i++){
        fi>>x[i]>>y[i];
        xg+=x[i];
        yg+=y[i];}
    xg/=n;
    yg/=n;
    s1=s2(xg,yg);
    c=100;
    while(c-0.000001>0){
        q=s2(xg+c,yg);
        if(q<s1) {s1=q;xg=xg+c;}
        q=s2(xg-c,yg);
        if(q<s1) {s1=q;xg-=c;}
        q=s2(xg,yg+c);
        if(q<s1) {s1=q;yg+=c;}
        q=s2(xg,yg-c);
        if(q<s1) {s1=q;yg-=c;}
        q=s2(xg+c,yg+c);
        if(q<s1) {s1=q;xg+=c;yg+=c;}
        q=s2(xg+c,yg-c);
        if(q<s1) {s1=q;xg+=c;yg-=c;}
        q=s2(xg-c,yg+c);
        if(q<s1) {s1=q;xg-=c;yg+=c;}
        q=s2(xg-c,yg-c);
        if(q<s1) {s1=q;xg-=c;yg-=c;}
        c/=2;}
    fo<<xg<<' '<<yg;
    return 0;
}