Cod sursa(job #1067765)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 27 decembrie 2013 14:58:10
Problema Adapost 2 Scor 80
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

int n;
double minnie = 200000000;
const int NMAX = 50001;
vector <pair <double, double> > coord;
pair <double, double> sol;

double dist(double x1, double y1, double x2, double y2){
  double a = (x2-x1) * (x2-x1);
  double b = (y2-y1) * (y2-y1);
  return sqrt(a+b);
}

void get_input(){
  ifstream in("adapost2.in");
  in>>n;
  for (int i = 1; i <= n; ++i){
    double x,y;
    in>>x>>y;
    cout<<x<<" "<<y<<"\n";
    coord.push_back(make_pair(x,y));
  }
  in.close();

}



double dist_total(double x1, double y1){
  double rez = 0;
  for (int i = 0; i<coord.size(); ++i)
    rez += dist( coord[i].first, coord[i].second,x1,y1);
  return rez;

}

void solve(){
  int ox[] = {-1,0,0,1}, oy[] = {0,-1,1,0};
  sol.first = 0;
  sol.second = 0;
  for (double pas = 1000; pas>0.001; pas/=2){
    int yep = 0;
    for (int i = 0; i<4; ++i){
      double x = sol.first + pas * ox[i];
      double y = sol.second + pas * oy[i];
      double d = dist_total(x,y);
      if (d<minnie){
        yep = 1;
        minnie = d;
        sol.first = x;
        sol.second = y;
        break;
      }
    }
    if (yep) pas *=2;
  }
}
int main(){
get_input();
solve();
ofstream out("adapost2.out");

out<<setprecision(3)<<fixed<<sol.first<<" "<<sol.second<<"\n";
out.close();
return 0;
}