Cod sursa(job #2137756)

Utilizator thepunisher38Tomulescu Ninel thepunisher38 Data 21 februarie 2018 00:41:01
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<algorithm>
#include<math.h>
using namespace std;
#define N_MAX 50002
#define EPS 0.000000001
int n,i;
typedef pair <double,double> p;
p a[N_MAX],centru;
double Min=1002*N_MAX;
double V=1002;
 
inline double dist(p a,p b)
{
    return sqrtl((double)(a.first-b.first)*(a.first-b.first)+(double)(a.second-b.second)*(a.second-b.second));
}
 
double CalcDist(p centru)
{
    double rez=0;
    for(int i=1;i<=n;i++)
        rez+=dist(centru,a[i]);
    return rez;
}
 
inline double modul(double x)
{
    if(x<0)
        return -x;
    return x;
}
 
void Solve(p centru)
{
    if(modul(V-EPS)<0.0000001)
    {
        printf("%lf %lf\n",centru.first,centru.second);
        exit(0);
    }
    double mij=CalcDist(centru);
    double st=CalcDist(p(centru.first-V,centru.second));
    double dr=CalcDist(p(centru.first+V,centru.second));
    double sus=CalcDist(p(centru.first,centru.second-V));
    double jos=CalcDist(p(centru.first,centru.second+V));
 
    double MIN=min(min(min(st,dr),min(sus,jos)),mij);
 
    if(modul(MIN-mij)<EPS)
    {
        V=(double)V/2;
        Solve(centru);
    }
    if(modul(MIN-st)<EPS)
    {
        Solve(p(centru.first-V,centru.second));
    }
    else
    if(modul(MIN-dr)<EPS)
    {
        Solve(p(centru.first+V,centru.second));
    }
    else
    if(modul(MIN-sus)<EPS)
    {
        Solve(p(centru.first,centru.second-V));
    }
    else
    if(modul(MIN-jos)<EPS)
    {
        Solve(p(centru.first,centru.second+V));
    }
}
 
int main()
{
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);
 
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i].first,&a[i].second);
        centru.first+=a[i].first;
        centru.second+=a[i].second;
    }
    centru.first/=n;
    centru.second/=n;
 
    Solve(centru);
    return 0;
}