Cod sursa(job #1874772)

Utilizator MKLOLDragos Ristache MKLOL Data 10 februarie 2017 13:39:02
Problema Adapost 2 Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 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.0001
ll N;
#define Nmax 1010100
double vx[202020];
double vy[202020];
double dist(double x1, double y1, double x2, double y2) {
  return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

double getdist(double x,double y) {
  double ret = 0;
  for(int i=0;i<N;++i) {
    ret += dist(x,y,vx[i],vy[i]);
  }
  return ret;
}
double X,Y;
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--) {
    double start = 1;
    while(start < 10000000) start *= 2;
    scanf("%d",&N);
    X = Y = 0;
    for(int i=0;i<N;++i) {
      double a,b;
      scanf("%lf%lf",&a,&b);
      X += a;
      Y += b;
      vx[i] = a;
      vy[i] = b;
    }
   // cout << v.size() << endl;
    //cout << v.size() << endl;
    X /= N;
    Y /= N;
    //cout << v.size() << endl;
    int NRQ = 0;
    while(start > eps) {
      int ok = 0;
      double curd = getdist(X,Y);
      double r = getdist(X+start,Y);
      double l = getdist(X-start,Y); 
      double d = getdist(X,Y-start);
      double u = getdist(X,Y+start);
      if(r < curd && u > curd && d > curd) {
        X=X+start;
        continue;
      }
      if(l < curd && u > curd && d > curd) {
        X=X-start;
        continue;
      }
      if(u < curd && l > curd && r > curd) {
        Y=Y+start;
        continue;
      }
      if(d < curd && l > curd && r > curd) {
        Y=-start;
        continue;
      }
      if(d <curd && l < curd) {
        double d1 = (curd - d);
        double d2 = (curd - l);
        X -= d2 / (d1+d2) * start;
        Y -= d1 / (d1+d2) * start;
        continue;
      }
      if(d <curd && r < curd) {
        double d1 = (curd - d);
        double d2 = (curd - r);
        X += d2 / (d1+d2) * start;
        Y -= d1 / (d1+d2) * start;
        continue;
      }
      if(u < curd && r < curd) {
        double d1 = (curd - u);
        double d2 = (curd - r);
        X += d2 / (d1+d2) * start;
        Y += d1 / (d1+d2) * start;
        continue;
      }
      if(u < curd && l < curd) {
        double d1 = (curd - u);
        double d2 = (curd - l);
        X -= d2 / (d1+d2) * start;
        Y += d1 / (d1+d2) * start;
        continue;
      }
      start = start / 2.0;
    }
    printf("%.12lf %.12lf\n",X, Y);
  }
}