Cod sursa(job #1054283)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 13 decembrie 2013 17:00:34
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.54 kb
#include <fstream>
#include <cmath>

using namespace std;

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

const int NMAX = 50001;
const int DIST = 150;
const int DIRECT = 5;
const double PREC = 0.00001;

const int dx[] = {0,0,0,1,-1};
const int dy[] = {0,1,-1,0,0};

class Point{

    public:
        double x,y;
    Point(double x_ = 0, double y_ = 0){
        x = x_;
        y = y_;
    }

}points[NMAX];

int N;

double distanceBetweenTwoPoints(const Point &a, const Point &b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double distanceToAllPoints(const Point &reper){
    double distance = 0;
    for(int i = 0; i < N; i++)
        distance += distanceBetweenTwoPoints(reper,points[i]);

    return distance;
}

int main()
{

    int pos, j;
    in >> N;

    for(j = 0; j < N; j++)
        in >> points[j].x >> points[j].y;

    Point reperPoint = points[0];
    Point aux;
    double minDist, auxDistance;

    for(double precission = DIST; precission >= PREC; precission /=2){
        //caut directia cea mai buna

        minDist = NMAX*1000;
        for(j = 0; j < DIRECT; j++){
            aux.x = reperPoint.x + dx[j]*precission;
            aux.y = reperPoint.x + dy[j]*precission;
            auxDistance = distanceToAllPoints(aux);
            if(auxDistance < minDist){
                minDist = auxDistance;
                pos = j;
            }
        }

        reperPoint.x += dx[pos]*precission;
        reperPoint.y += dy[pos]*precission;

    }
    out << reperPoint.x << ' ' << reperPoint.y << '\n';
    return 0;
}