Cod sursa(job #1071008)

Utilizator dariusdariusMarian Darius dariusdarius Data 2 ianuarie 2014 14:26:51
Problema Adapost 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

#include<algorithm>
#include<fstream>
#include<iomanip>
using namespace std;
const int MAX_N=50000+5;
const double MAX_PAS=100.0;
const double EPS=0.0000000001;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
class PointXY {
public:
    PointXY() { x = y = 0.0; }
    PointXY(double xx, double yy) { x = xx; y = yy; }
    inline double operator*(const PointXY &other) const {
        return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
    }
    inline void set(const PointXY &other, const double &delta_x, const double &delta_y) {
        x = other.x + delta_x;
        y = other.y + delta_y;
    }
    inline void read(ifstream &fin) {
        fin >> x >> y;
    }
    inline void write(ofstream &fout) {
        fout << setprecision(4) << fixed;
        fout << x << " " << y << endl;
    }
    inline double getx() {
        return x;
    }
    inline double gety() {
        return y;
    }
    inline void divide(const int &n) {
        x/=n;
        y/=n;
    }
private:
    double x,y;
};
int n;
PointXY points[MAX_N];
double cost(const PointXY &point) {
    double answer=0.0;
    for(int i = 1; i <= n; ++i) {
        answer += point * points[i];
    }
    return answer;
}
int main() {
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    PointXY answer(0,0),next_answer;
    fin >> n;
    for(int i = 1; i <= n; ++i) {
        points[i].read(fin);
        answer.set(answer, points[i].getx(), points[i].gety());
    }
    answer.divide(n);
    double current_best_cost = cost(answer), current_cost;
    for(double pas = MAX_PAS; pas >= EPS; pas *= 0.5) {
        bool increase_pas=false;
        for(int d = 0; d < 4; ++d) {
            next_answer.set(answer,pas * dx[d], pas * dy[d]);
            current_cost=cost(next_answer);
            if(current_best_cost - current_cost >= EPS) {
                current_best_cost = current_cost;
                answer = next_answer;
                increase_pas=true;
            }
        }
        if(increase_pas) {
            pas*=2.0;
        }
    }
    answer.write(fout);
    return 0;
}