Cod sursa(job #2285097)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 18 noiembrie 2018 09:37:54
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 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 = 1e-4;
 
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(double i=100;i > EPS;i /= 1.4)
    {
        double up = suma(make_pair(c.x - i, c.y));
        double down = suma(make_pair(c.x + i, c.y));
        double left = suma(make_pair(c.x, c.y - i));
        double right = suma(make_pair(c.x, c.y + i));
 
        double minx = min( up,down,left,right);
        if(minx == up) c.x-=i;
        if(minx == down) c.x+=i;
        if(minx == left) c.y-=i;
        if(minx == right) c.y+=i;
    }
 
    printf("%.5f %.5f",c.x,c.y);
}