Cod sursa(job #2303035)

Utilizator AlexToveAlexandru Toader AlexTove Data 15 decembrie 2018 14:00:49
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.57 kb
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
const int NMAX=50000;
const double eps=0.001;
struct point
{
    double x, y;
};
point adapost, nadapost;
point v[NMAX+5];
int dx[4]={0, 1, 0, -1};
int dy[4]={1, 0, -1, 0};
int n;
double dist(point p1, point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double dist_tot(point a)
{
    double suma=0;
    for(int i=1;i<=n;i++)
        suma=suma+dist(a, v[i]);
    return suma;
}
int main()
{
    int i;
    bool ok=0;
    double distanta_minima, distanta, pas=1000;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        adapost.x=adapost.x+v[i].x;
        adapost.y=adapost.y+v[i].y;
    }
    adapost.x=adapost.x/n;
    adapost.y=adapost.y/n;
    //adapost trebuie sa fie initializat cu un pct din interior, asa ca pt a fi sigur de acest lucru, l-am initializat cu coordonatele elementului median
    distanta_minima=dist_tot(adapost);
    while(pas>eps)
    {
       ok=1;
       for(i=0;i<4;i++)
       {
           nadapost.x=adapost.x+pas*dx[i];
           nadapost.y=adapost.y+pas*dy[i];
           distanta=dist_tot(nadapost);
           if(distanta<distanta_minima)
           {
               distanta_minima=distanta;
               adapost.x=nadapost.x;
               adapost.y=nadapost.y;
               ok=0;
               break;
           }
       }
       if(ok==1)
        pas=pas*0.5;
    }
    fout<<adapost.x<<" "<<adapost.y<<"\n";
    return 0;
}