Cod sursa(job #795277)

Utilizator vendettaSalajan Razvan vendetta Data 7 octombrie 2012 22:55:04
Problema Adapost 2 Scor 61
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <cmath>

using namespace std;

ifstream f("adapost2.in");
ofstream g("adapost2.out");

#define nmax 50005
#define ll long long

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int n;
pair<double,double> v[nmax];
double Xx, Yy;

void citeste(){

    f >> n;
    for(int i=1; i<=n; ++i){
        double x, y;
        f >> x >> y;
        v[i] = make_pair(x,y);
        Xx += x;
        Yy += y;
    }

}

double incearca(double X, double Y){

    double cat = 0.0000;
    for(int i=1; i<=n; ++i){
        double A = (v[i].first - X) * (v[i].first - X);
        double B = (v[i].second - Y) * (v[i].second - Y);
        double xx = sqrt(A+B);
        cat += xx;
    }

    return cat;

}

void rezolva(){

    //ideea ar fi ca pornesc dintr-un punct si incerc sa ma apropii de punctul dorit
    double dist = 1454565454000.0;
    double X = Xx/double(n);
    double Y = Yy/double(n);
    double Min = incearca(X,Y);
    double Solx = X;
    double Soly = Y;
    while(dist > 0.0001){
        for(int i=0; i<4; ++i){
            double xx = X + (double(dx[i]) * dist);
            double yy = Y + (double(dy[i]) * dist);
            double cat = incearca(xx,yy);
            if (cat < Min){
                Min = cat;
                Solx = xx;
                Soly = yy;
                break;
            }
        }
        X = Solx;
        Y = Soly;
        dist = dist / 1.5;
    }

    g << Solx << " " << Soly << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}