Cod sursa(job #528561)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 2 februarie 2011 23:25:01
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 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],r;
float err, s, sc,s1,s2,s3,s4,sx,sy,pace,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;
    for(i=2; i<=n; i++)
    {
        in>>p[i].x>>p[i].y;
        sx += p[i].x;
        sy += p[i].y;
    }

    r = point(sx/n, sy/n);
    pace = 100;
    err = 1<<29;
    s = suma_dist(r);
    while(err > 0.0001 && ++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)
            r.x -= pace;
        else if(s2 == sc)
            r.x += pace;
        else if(s3 == sc)
            r.y -= pace;
        else if(s4 == sc)
            r.y += pace;
        
        err = s - sc;
        s = sc;
    }

    out<<suma_dist(r)<<'\n'<<suma_dist(point(4.1442, 4.2898))<<"\n\n";

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

    return 0;
}