Cod sursa(job #3232626)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 31 mai 2024 17:09:31
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<bits/stdc++.h>
using namespace std;
ifstream F("adapost2.in");
ofstream G("adapost2.out");
pair<double,double> a[50000];
int n,z[]={-1,0,1,0},i;
double x,y,e=0.001,f,s=100.0,u,v,t;
bool d;
double A(double x,double y)
{
    double r=0,u,v;
    int i;
    for(i=0;i<n;u=a[i].first-x,v=a[i++].second-y,r+=sqrt(u*u+v*v));
    return r;
}
int main()
{
    for(F>>n;i<n;F>>a[i].first>>a[i].second,x+=a[i].first,y+=a[i].second,++i);
    for(x/=n,y/=n,f=A(x,y);s>e;) {
        for(d=0,i=0;i<4;++i)
            if(u=s*z[i]+x,v=s*z[3-i]+y,t=A(u,v),t<f) {
                f=t,x=u,y=v,d=1;
                break;
            }
        if(!d)
            s/=2;
    }
    return G<<fixed<<setprecision(4)<<x<<' '<<y,0;
}