Cod sursa(job #1998836)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 9 iulie 2017 12:48:15
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
using namespace std;
typedef double f64;

const int NMAX = 50005;

struct PTX {
    f64 x, y;

    inline PTX() { }
    inline PTX(f64 _x, f64 _y) {
        x = _x;
        y = _y;
    }

    friend ifstream& operator >> (ifstream &fs, PTX &arg) {
        fs>>arg.x>>arg.y;
        return fs;
    }
    friend ofstream& operator << (ofstream &fs, PTX &arg) {
        fs<<arg.x<<' '<<arg.y;
        return fs;
    }
};

int n;
PTX pts[NMAX];

inline f64 dist(const PTX &a, const PTX &b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

inline f64 sdist(const PTX &arg) {
    f64 sum = 0.;
    for(int i=0; i<n; ++i)
        sum+= dist(arg, pts[i]);

    return sum;
}

int sx[] = {0, 1, -1,  0},
    sy[] = {1, 0,  0, -1};

int main(void) {
    ifstream fi("adapost2.in");
    ofstream fo("adapost2.out");
    bool flag;
    PTX  tmp, ant(500., 500.);
    f64  cdt, tdt, p;
    int  lim;

    fi>>n;
    for(int i=0; i<n; ++i)
        fi>>pts[i];

    cdt = sdist(ant);
    p = 256.;

    lim = 38;
    if(n<10000)
        lim = 50;
    for(int stp=0; stp<lim; ++stp) {
        for(int i=0; i<4; ++i) {
            tmp.x = ant.x + p * sx[i];
            tmp.y = ant.y + p * sy[i];
            tdt   = sdist(tmp);

            if(tdt < cdt) {
                cdt = tdt;
                ant = tmp;
                p  *= 2.;
                break;
            }
        }
        p/= 2;
    }

    fo<<ant<<'\n';

    fi.close();
    fo.close();
    return 0;
}