Cod sursa(job #1081657)

Utilizator IoannaPandele Ioana Ioanna Data 13 ianuarie 2014 20:01:06
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.92 kb
#include <fstream>
#include <cmath>
#define eps 0.00000000001
#define dlim 0.0001
#define NMAX 50000
using namespace std;

struct point {
    double x, y;
};

point p[50000];
point g, sol;
int n;
double minimul;

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

void read() {
    in>>n;
    for (int i = 0; i < n; i++)  {
        in>>p[i].x>>p[i].y;
        g.x = g.x + p[i].x;
        g.y = g.y + p[i].y;
    }
    g.x = g.x / n;
    g.y = g.y / n;
}

int minim(double dist[]) {
    double minimul = dist[0];
    int k = 0;
    for (int i = 1; i <= 4; i ++) {
        if (minimul - dist[i] >= eps) {
            k = i;
            minimul = dist[i];
        }
    }
    return k;
}

double distanta(point a) {
    double dist = 0;
    for (int i = 0; i < n; i++) {
        dist = dist + sqrt((a.x - p[i].x) * (a.x - p[i].x) + (a.y - p[i].y) * (a.y - p[i].y));
    }
    return dist;
}

void cauta(point a, double d) {
    double dist;
    double dsol = distanta(a);
    point p;

    while (d > 0.0001) {

        p.x = a.x + d;
        p.y = a.y;
        dist = distanta(p);

        if (dsol > dist) {
            dsol = dist;
            a = p;
            continue;
        }

        p.x = a.x - d;
        p.y = a.y;
        dist = distanta(p);

        if (dsol > dist) {
            dsol = dist;
            a = p;
            continue;
        }

        p.x = a.x;
        p.y = a.y + d;
        dist = distanta(p);

        if (dsol > dist) {
            dsol = dist;
            a = p;
            continue;
        }

        p.x = a.x;
        p.y = a.y - d;
        dist = distanta(p);
        if (dsol > dist) {
            dsol = dist;
            a = p;
            continue;
        }
        d = d/2;
    }
    out<<a.x<<" "<<a.y;
}

int main() {
    read();
    cauta(g, 200);
    //out<<sol.x<<" "<<sol.y;
    return 0;
}