Cod sursa(job #2081439)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 4 decembrie 2017 18:36:39
Problema Adapost 2 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <cmath>
#include <utility>      // std::pair


#define NMAX 50010
#define x first
#define y second

using namespace std;

typedef struct pair<double, double> Punct;

Punct p[NMAX];
int N;
double EPS = 100;

double dist(Punct a, Punct b)
{
    return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}

double suma(Punct c)
{
    double sm = 0;
    for(int i=0;i<N;++i)
        sm += dist(c,p[i]);

    return sm;
}

double min(double a,double b, double c,double d)
{
    if(a <= b && a<=c && a<=d) return a;
    if(b <= c && b<=a && b<=d) return b;
    if(c <= a && c<=d && c<=b) return c;
    if(d <= a && d<=b && d<=c) return d;

}

int main()
{
    int i;
    double smx=0,smy=0;
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);

    scanf("%d",&N);
    for(i=0;i<N;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        smx += p[i].x;
        smy += p[i].y;
    }

    Punct c = make_pair(smx/N, smy/N);//centrul de greutate

    for(;EPS > 0.01;EPS /= 1.2)
    {
        double up = suma(make_pair(c.x - EPS, c.y));
        double down = suma(make_pair(c.x + EPS, c.y));
        double left = suma(make_pair(c.x, c.y - EPS));
        double right = suma(make_pair(c.x, c.y + EPS));

        double minx = min( up,down,left,right);
        if(minx == up) c.x-=EPS;
        if(minx == down) c.x+=EPS;
        if(minx == left) c.y-=EPS;
        if(minx == right) c.y+=EPS;
    }

    printf("%.4f %.4f",c.x,c.y);
}