Cod sursa(job #1874737)

Utilizator MKLOLDragos Ristache MKLOL Data 10 februarie 2017 13:14:12
Problema Adapost 2 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
// TEAM CORNELL
#include<bits/stdc++.h>

#define fs first
#define sc second
#define mp make_pair
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef pair<double,double> pdd;
#define eps 0.00001
ll N;
#define Nmax 1010100
vector<pdd> v;
double dist(pdd &a, pdd &b) {
  return sqrt((1.0*a.fs-b.fs) *(1.0*a.fs-b.fs) + (1.0*a.sc - b.sc) * (1.0*a.sc-b.sc));
}

double getdist(pdd x) {
  double ret = 0;
  for(auto a : v) {
    ret += dist(a,x);
  }
  return ret;
}
int T=0;
map<double,int> h;
int main() {
  freopen("adapost2.in","r",stdin);
  freopen("adapost2.out","w",stdout);
  cin.sync_with_stdio(false);
 // cin >> T;
 T=1;
  while(T--) {
    v.clear();
    double start = 1;
    while(start < 10000) start *= 2;
    pdd cur=mp(0,0);
    cin >> N;
    for(int i=0;i<N;++i) {
      double a,b;
      cin >> a >> b;
      cur.fs += a;
      cur.sc += b;
      v.pb(mp(a,b));
    }
   // cout << v.size() << endl;
    //cout << v.size() << endl;
    cur.fs /= N;
    cur.sc /= N;
    //cout << v.size() << endl;
    double curd = getdist(cur);
    int NRQ = 0;
    while(start > eps) {
      int ok = 0;
      double nd = getdist(mp(cur.fs+start,cur.sc));
      if(nd < curd) {
        cur.fs = cur.fs + start;
        curd=nd;
        ok = 1;
        continue;
      }
      nd = getdist(mp(cur.fs-start,cur.sc)); 
      if(nd < curd) {
        cur.fs = cur.fs - start;
        curd=nd;
        ok = 1;
        continue;
      }
      nd = getdist(mp(cur.fs,cur.sc-start));
      if(nd < curd) {
        cur.sc = cur.sc - start;
        curd=nd;
        ok = 1;
        continue;
      }
      nd = getdist(mp(cur.fs,cur.sc+start));
      if(nd < curd) {
        cur.sc = cur.sc + start;        
        curd=nd;
        ok = 1;
        continue;
      }
      if(!ok || NRQ > 4) {
        start = start / 2.0;
        NRQ = 0;
      } else {
        ++NRQ;
      }
    }
    printf("%.12lf %.12lf\n",cur.fs, cur.sc);
  }
}