Cod sursa(job #1054151)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 13 decembrie 2013 13:53:11
Problema Adapost 2 Scor 59
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.14 kb
#include<fstream>
#include<iomanip>
#include<cmath>
using namespace std;
typedef struct { double x,y; } punct;
int n,i;
punct a[50005];
double px,py,dn,ds,de,dv;
bool ok=1;

double dist(double x, double y) {
       double rez=0;
       for (int i=1; i<=n; ++i) rez+=sqrt( (x-a[i].x)*(x-a[i].x) + (y-a[i].y)*(y-a[i].y) );
       return(rez);
}

int main(void) {
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    fin>>n;
    for (i=1; i<=n; ++i) {
           fin>>a[i].x>>a[i].y;
           px+=a[i].x; py=a[i].y;
           }
    px/=n; py/=n; double prec=5, s=dist(px,py);
    while (prec>=0.0001) {
          ok=1;
            while (ok) {
                  ok=0;
                  dn=dist(px,py-prec); ds=dist(px,py+prec); dv=dist(px-prec,py); de=dist(px+prec,py);
                   if (dn<s) { s=dn; py-=prec; ok=1; }
                   if (ds<s) { s=ds; py+=prec; ok=1; }
                   if (de<s) { s=de; px+=prec; ok=1; }
                   if (dv<s) { s=dv; px-=prec; ok=1; }
                   }
             prec/=2;
             }
    fout<<setprecision(4)<<fixed<<px<<" "<<py;
 return(0);
}