Cod sursa(job #1006775)

Utilizator misinozzz zzz misino Data 7 octombrie 2013 18:48:27
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<fstream>
#include<cmath>
#include<cstdio>
#define punct pair<double,double>
#define x first
#define y second
#define N 500109
using namespace std;
ofstream g("adapost2.out");
int  i,n,d;
punct v[N],pnou;
double x,y,x11,y11,pas,sol,dist1,dist;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
const double eps=0.00005;
inline double distp(punct a,punct b)
{
    return (double)sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline int compara(double a,double b)
{
    if(a-b<-eps)
    return -1;
    if(a-b>eps)
    return 1;
    return 0;
}
int main()
{
    freopen("adapost2.in","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        x+=v[i].x;
        y+=v[i].y;
    }
    pas=100;
    x/=(double)n;
    y/=(double)n;
    sol=2000000000000.0;
    while(compara(pas,eps)>0)
    {
        dist1=sol;
        for(d=0;d<=3;++d)
        {
            pnou.x=x+dx[d]*pas;
            pnou.y=y+dy[d]*pas;
            dist=0;
            for(i=1;i<=n;++i)
            dist+=distp(pnou,v[i]);
            if(compara(dist,sol)<0)
            sol=dist,
            x11=pnou.x,
            y11=pnou.y;
        }
        if(compara(sol,dist1)==0)
        pas=(double)pas/2.0;
        else
        x=x11,y=y11;
    }
    g<<x<<' '<<y<<'\n';
    return 0;
}