Cod sursa(job #1054674)

Utilizator vlad.florescu94FMI Florescu Vlad - Adrian vlad.florescu94 Data 14 decembrie 2013 01:32:44
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.65 kb
#include<fstream>
#include<cmath>
#include<iomanip>
#define numar 1000001
using namespace std;
ifstream f("adapost2.in");
ofstream g("adapost2.out");
struct punct{
double x,y;
};
struct tampita{
 int poz;
 double lung;
};
int n,i,rasp;
punct v[50001],p,pe[5];
double mini,l=500.0,sum[5],init;

int minim(double rau,double a,double b,double c,double d)
{
  tampita unu,doi,tri;
  if(a<b) {unu.poz=1;unu.lung=a;} else {unu.poz=2;unu.lung=b;}
  if(c<d) {doi.poz=3;doi.lung=c;} else {doi.poz=4;doi.lung=d;}

  if(unu.lung<doi.lung)
    {tri.lung=unu.lung;tri.poz=unu.poz;}
  else
    {tri.lung=doi.lung;tri.poz=doi.poz;}

  if(tri.lung<rau)
    return tri.poz;
  else
    return numar;
}
double dist(punct a,punct b)
{
  return sqrt(pow(b.x-a.x,2)+pow(b.y-a.y,2));
}
double sum_dist(punct p)
{
    double suma=0;
    int i;
    for(i=1;i<=n;i++)
      suma+=dist(p,v[i]);
    return suma;
}

int main()
{
  f>>n;
  for(i=1;i<=n;i++)
    f>>v[i].x>>v[i].y;

  p.x=p.y=500.0;
  while(l>0.0001)
  {
  //    g<<p.x<<" "<<p.y<<" ----> ";
      init=sum_dist(p);// g<<init<<'\n';

      pe[1].x=p.x+l;pe[1].y=p.y;
      pe[2].x=p.x-l;pe[2].y=p.y;
      pe[3].x=p.x;pe[3].y=p.y+l;
      pe[4].x=p.x;pe[4].y=p.y-l;
      sum[1]=sum_dist(pe[1]);sum[2]=sum_dist(pe[2]);sum[3]=sum_dist(pe[3]);sum[4]=sum_dist(pe[4]);
//      g<<sum[1]<<" ! "<<sum[2]<<" ! "<<sum[3]<<" ! "<<sum[4]<<" ! "<<'\n'<<'\n';
      rasp=minim(init,sum[1],sum[2],sum[3],sum[4]);

      if(rasp!=numar)
        p=pe[rasp];
      l/=1.41421356237; // asta e radical din 2
  }
 g<<fixed;
 g<<setprecision(4)<<p.x<<" "<<p.y;
 f.close();g.close();
 return 0;
}