Cod sursa(job #795271)

Utilizator vendettaSalajan Razvan vendetta Data 7 octombrie 2012 22:48:19
Problema Adapost 2 Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 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

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 = 1000;
    double X = Xx/double(n);
    double Y = Yy/double(n);
    double Min = incearca(X,Y);
    double Solx = X;
    double Soly = Y;
    while(dist > 0.00001){
        //ma duc in sus
        Solx = X;
        Soly = Y;
        double xx = X - dist;
        double yy = Y;
        double val = incearca(xx,yy);
        if ( val < Min ){
            Min = val;
            Solx = xx;
            Soly = yy;
        }
        //ma duc in jos
        xx = X + dist;
        yy = Y;
        val = incearca(xx,yy);
        if (val < Min){
            Min = val;
            Solx = xx;
            Soly = yy;
        }

        //ma duc in stanga
        xx = X;
        yy = Y - dist;
        val = incearca(xx,yy);
        if (val < Min){
            Min = val;
            Solx = xx;
            Soly = yy;
        }
        xx = X;
        yy = Y + dist;
        val = incearca(xx,yy);
        if (val < Min){
            Min = val;
            Solx = xx;
            Soly = yy;
        }
        X = Solx;
        Y = Soly;
        dist = dist / 1.5;
    }

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

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}