Cod sursa(job #1046919)

Utilizator geniucosOncescu Costin geniucos Data 3 decembrie 2013 18:30:50
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<cstdio>
#include<cmath>
using namespace std;
int i,n,how,k;
double ceva,xmi,ymi,xma,yma,rat,mini,C[6],xs,ys,xp,yp,x[50009],y[50009];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
double cost(double X,double Y)
{
    int i;
    double ras=0;
    if(X<xmi||Y<ymi||Y>yma||X>xma) return 1000000000;
    for(i=1;i<=n;i++)
        ras=(double)ras+sqrt((X-x[i])*(X-x[i])+(Y-y[i])*(Y-y[i]));
    return ras;
}
int main()
{
freopen("adapost2.in","r",stdin);
freopen("adapost2.out","w",stdout);
scanf("%d",&n);
xmi=ymi=1000000;
for(i=1;i<=n;i++)
{
    scanf("%lf%lf",&x[i],&y[i]);
    if(x[i]<xmi) xmi=x[i];
    if(y[i]<ymi) ymi=y[i];
    if(x[i]>xma) xma=x[i];
    if(y[i]>yma) yma=y[i];
}
xs=xmi;
ys=ymi;
mini=cost(xs,ys);
rat=2000;
while(rat>=0.00005)
{
    ceva=cost(xs+rat,ys);
    if(ceva<mini)
    {
        mini=ceva;
        xs=xs+rat;
        continue;
    }
    ceva=cost(xs-rat,ys);
    if(ceva<mini)
    {
        mini=ceva;
        xs=xs-rat;
        continue;
    }
    ceva=cost(xs,ys+rat);
    if(ceva<mini)
    {
        mini=ceva;
        ys=ys+rat;
        continue;
    }
    ceva=cost(xs,ys-rat);
    if(ceva<mini)
    {
        mini=ceva;
        ys=ys-rat;
        continue;
    }
    rat/=2;
}
printf("%.4lf %.4lf\n",xs,ys);
return 0;
}