Cod sursa(job #1081616)

Utilizator IoannaPandele Ioana Ioanna Data 13 ianuarie 2014 19:28:22
Problema Adapost 2 Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <cmath>
#define eps 0.00000000001
#define dlim 0.000001
#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[5];
    point p[5];

    if (dlim - d >= eps) {
        return;
    }
    p[0] = a;
    dist[0] = distanta(a);

    p[1].x = a.x + d;
    p[1].y = a.y;
    dist[1] = distanta(p[1]);
    p[2].x = a.x - d;
    p[2].y = a.y;
    dist[2] = distanta(p[2]);
    p[3].x = a.x;
    p[3].y = a.y + d;
    dist[3] = distanta(p[3]);
    p[4].x = a.x;
    p[4].y = a.y - d;
    dist[4] = distanta(p[4]);

    int k = minim(dist);
    sol = p[k];
    cauta(p[k], d/2);
}

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