Cod sursa(job #528489)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 2 februarie 2011 22:00:26
Problema Adapost 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 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;
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);
    }

    ss = point(minx, miny);
    ds = point(maxx, miny);
    sj = point(minx, maxy);
    dj = point(maxx, maxy);
    s = 1<<29;

    err = 1<<29;

    while(err > 0.0000001)
    {
        m = point((ss.x+ds.x)/2, (ss.y+sj.y)/2);
        s1 = suma_dist(ss);
        s2 = suma_dist(ds);
        s3 = suma_dist(sj);
        s4 = suma_dist(dj);
        sc = min(min(s1,s2),min(s3,s4));
        if(sc == s1)
        {
            // stanga sus
            ds.x = m.x;
            sj.y = m.y;
            dj = m;
            r = ss;
        }
        else if(sc == s2)
        {
            // dreapta sus
            ss.x = m.x;
            dj.y = m.y;
            sj = m;
            r = ds;
        }
        else if(sc == s3)
        {
            // stanga jos
            ss.y = m.y;
            dj.x = m.x;
            ds = m;
            r = sj;
        }
        else if(sc == s4)
        {
            // dreapta jos
            sj.x = m.x;
            ds.y = m.y;
            ss = m;
            r = dj;
        }
        err = abs(sc - s);
        s = sc;
    }

    //out<<suma_dist(point(r.x, r.y))<<endl;
    //out<<suma_dist(point(4.1442,4.2898))<<endl<<endl;

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

    return 0;
}