Cod sursa(job #528675)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 3 februarie 2011 10:05:45
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
// infoarena: problema/adapost2 //
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;

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

const int MAXN = 50010;
const float err = 0.00001;

int n,m,i,j;

template<typename T>
struct point
{
    T x,y;
    point(){}
    point(T _x, T _y)
    {
        x = _x;
        y = _y;
    }
    T distance(point<T> other)
    {
        return sqrt((x-other.x)*(x-other.x) + (y-other.y)*(y-other.y));
    }

    T distance_sum(vector<point<T> > a)
    {
        T r=0;
        typeof(a.begin()) it, end = a.end();
        for(it=a.begin(); it!=end; it++)
            r += distance(*it);
        return r;
    }
};

vector<point<float> > v;
point<float> r,  tmp;
float sx, sy, pace, s1, s2, s3, s4, s, sc;

int main()
{
    in>>n>>m;
    for(i=0; i<n; i++)
    {
        in>>tmp.x>>tmp.y;
        v.push_back(tmp);
        sx += tmp.x;
        sy += tmp.y;
    }

    r = point<float>(sx/n, sy/n);
    s = r.distance_sum(v);
    pace = 100;
    while(pace > err)
    {
        s1 = point<float>(r.x-pace, r.y).distance_sum(v);
        s2 = point<float>(r.x+pace, r.y).distance_sum(v);
        s3 = point<float>(r.x, r.y-pace).distance_sum(v);
        s4 = point<float>(r.x, r.y+pace).distance_sum(v);
        sc = min(min(s1,s2), min(s3,s4));

        if(s < sc)
        {
            pace /= 2;
            continue;
        }

        if(s1 == sc)
            r.x -= pace;
        else if(s2 == sc)
            r.x += pace;
        else if(s3 == sc)
            r.y -= pace;
        else if(s4 == sc)
            r.y += pace;

        s = sc;
    }

    //out<<r.distance_sum(v)<<'\n'<<point<float>(4.1442, 4.2898).distance_sum(v)<<"\n\n";
    out<<r.x<<' '<<r.y;

    return 0;
}