Cod sursa(job #2304772)

Utilizator stan_flaviusStan Flavius Stefan stan_flavius Data 18 decembrie 2018 16:35:35
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#define nmax 500001

using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

struct pct
{ double x,y;
};

pct a[nmax];
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
pct punctC; ///centrul
pct PctMin;

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

double CalcDist(pct punct)
{ double s=0;
  for(int i=1; i<=n; i++)
      s+=distPct(a[i],punct);
  return s;
}

int main()
{
  int i;
  fin>>n;
  double Sx=0,Sy=0;
  for(i=1; i<=n; i++)
      { fin>>a[i].x>>a[i].y;
        Sx+=a[i].x;
        Sy+=a[i].y;
      }
  punctC.x=Sx/n;
  punctC.y=Sy/n;

  double prec=100;
  double variatie=0.001;

  double distmn=CalcDist(punctC);
  PctMin=punctC;
  while(prec>variatie)
      { double mn=1000000000;
        pct PctMinInt;
        for(i=0; i<4; i++)
            { pct punct;
              punct.x=PctMin.x+dx[i]*prec;
              punct.y=PctMin.y+dy[i]*prec;
              double dist=CalcDist(punct);
              if(dist<mn) {mn=dist; PctMinInt=punct;}
            }

        if(mn<distmn) {distmn=mn; PctMin=PctMinInt;}
        else prec/=2;
      }

  fout<<fixed<<setprecision(4)<<PctMin.x<<" ";
  fout<<fixed<<setprecision(4)<<PctMin.y;
    return 0;
}