Cod sursa(job #528520)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 2 februarie 2011 22:44:52
Problema Adapost 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
// infoarena: problema/adapost2 //
#include <fstream>
#include <cmath>
using namespace std;

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

const int MAXN = 50000;

struct point {
    float x,y;
    point(){}
    point(float _x, float _y)
    {
        x = _x;
        y = _y;
    }
};

point p[MAXN], ds, ss, dj, sj,r,m;
float maxx, minx, maxy, miny, err, s, sc,s1,s2,s3,s4,sx,sy,pace,delta,steps;
int i,n;

inline float dist(point a, point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

inline float suma_dist(point a)
{
    float r=0;
    for(i=1; i<=n; i++)
        r+=dist(a, p[i]);
    return r;
}

int main()
{
    in>>n;
    in>>p[1].x>>p[1].y;
    maxx = minx = p[1].x;
    maxy = miny = p[1].y;
    for(i=2; i<=n; i++)
    {
        in>>p[i].x>>p[i].y;
        maxx = max(maxx, p[i].x);
        minx = min(minx, p[i].x);
        maxy = max(maxy, p[i].y);
        miny = min(miny, p[i].y);
        sx += p[i].x;
        sy += p[i].y;
    }

    r = point(sx/n, sy/n);
    pace = maxx+maxy-minx-miny;
    err = 1<<29;
    s = suma_dist(r);
    delta = 0;
    while(steps++ < 100000)
    {
        s1 = suma_dist(point(r.x-pace, r.y)); // left
        s2 = suma_dist(point(r.x+pace, r.y)); // right
        s3 = suma_dist(point(r.x, r.y-pace)); // up
        s4 = suma_dist(point(r.x, r.y+pace)); // down
        sc = min(min(s1,s2),min(s3,s4));
        if(sc > s)
        {
            pace /= 2;
            continue;
        }
        if(s1 == sc)
        {
            // left
            r.x -= pace;
            err = s - sc;
        }
        if(s2 == sc)
        {
            // right
            r.x += pace;
            err = s - sc;
        }
        if(s3 == sc)
        {
            // up
            r.y -= pace;
            err = s - sc;
        }
        if(s4 == sc)
        {
            // down
            r.y += pace;
            err = s - sc;
        }
        if(err != 1<<29)
        {
            pace = err/(3*n);
            if(pace < 0.01)
                pace = 0.01;
        }
        s = sc;
    }

    out<<r.x<<' '<<r.y;

    return 0;
}