Cod sursa(job #2274798)

Utilizator marian013Giugioiu Marian Constantin marian013 Data 2 noiembrie 2018 15:15:01
Problema Adapost 2 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>
#include <math.h>
using namespace std;
int n;
int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
struct punct{
    double x, y;
}cg,v[50003];
double dist(punct a, punct b){
    int x1 = a.x - b.x;
    int y1 = a.y - b.y;
    x1 *= x1;
    y1 *= y1;
    return sqrt(x1 + y1);
}
double dist_centru(punct centru)
{
    int sum = 0;
    for(int i = 1; i <= n; ++i)
        sum += dist(centru, v[i]);
    return sum;
}
int main()
{
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
        cg.x += v[i].x;
        cg.y += v[i].y;
    }
    cg.x /= n;
    cg.y /= n;
    punct s = cg;
    double dist_s = dist_centru(s);
    double k = 1000;
    while(k > 0.0001)
    {
        punct e;
        double dist_e = 10000000000;
        for(int i = 0; i < 4; ++i)
        {
            punct j;
            j.x = s.x + k * dx[i];
            j.y = s.y + k * dy[i];
            double dist_j = dist_centru(j);
            if(dist_j < dist_e)
            {
                dist_e = dist_j;
                e = j;
            }
        }
        if(dist_e < dist_s)
        {
            dist_s = dist_e;
            s = e;
        }
        else
            k /= 2;
    }
    printf("%.5lf %.5lf",s.x, s.y);
    return 0;
}