Cod sursa(job #1838963)

Utilizator BLz0rDospra Cristian BLz0r Data 2 ianuarie 2017 01:24:31
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;

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

#define MAXITR 40 /* GASIT EXPERIMENTAL */

class Point {
 public:
    double x, y;

    Point(){
    }

    Point(const double x, const double y) {
        this->x = x;
        this->y = y;
    }

};

//functie ce returneaza distanta intre 2 puncte
inline double dist(Point A, Point B) {

    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

int N;
vector <Point> v;

//functie ce returneaza suma distantelor de la un punct la toate cele date
double distToAll(Point A) {

    double sum = 0;

    for (int i = 1; i <= N; ++i)
        sum += dist(v[i], A);

    return sum;
}

const int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; //vector de directii

Point Bsearch(Point A) { //cautam punctul dorit

    Point solPoint = A;
    double solDist = distToAll(A);

    double Step = 256.0; //pasul de modificare al punctului

    for (int itr = 1; itr <= MAXITR; ++itr) {

        double nextStep = Step * 0.5; //potentialul pas urmator

        double x = solPoint.x;
        double y = solPoint.y;

        for (int i = 0; i < 4; ++i) { //incerc sa il duc in toate cele 4 directii

            double xx = x + dir[i][0] * Step;
            double yy = y + dir[i][1] * Step;

            Point auxPoint = Point(xx, yy);  //noul punct obtinut

            double auxDist = distToAll(auxPoint); //ii calculez distanta totala

            if (auxDist < solDist) { //daca e mai buna
                solDist = auxDist; //actualizez distanta
                solPoint = auxPoint; //actualizez punctul
                nextStep = Step; //las acelasi pas, poate ajuta in continuare
            }
        }

        Step = nextStep; //setez noul pas (sau ramane acelasi)
    }

    return solPoint; //rezultatul
}

string Buffer;
string :: iterator it;

int readInt() {

    int nr = 0;

    while (*it < '0' || *it > '9')
        it++;

    while (*it >= '0' && *it <= '9') {
        nr = nr * 10 + (*it - '0');
        it++;
    }

    return nr;
}

double readDouble() {

    return 1.0 * readInt() + 0.001 * readInt();
}

int main() {

    getline(fin, Buffer, (char)0);
    it = Buffer.begin();

    N = readInt();

    v.resize(N + 2);

    //citire
    double x, y, medX = 0, medY = 0;
    for (int i = 1; i <= N; ++i) {

        x = readDouble();
        y = readDouble();

        v[i] = Point(x, y);

        medX += x;
        medY += y;
    }

    medX /= N;
    medY /= N;

    Point sol = Bsearch(Point(medX, medY)); //pornim de la centrul de greutate

    //afisare
    fout << fixed << setprecision(4);
    fout << sol.x << " " << sol.y;

    return 0;
}