Cod sursa(job #1074568)

Utilizator cdascaluDascalu Cristian cdascalu Data 7 ianuarie 2014 19:21:43
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.55 kb
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <stack>
#include <unordered_map>
#define Nmax 50001
using namespace std;

double X[Nmax],Y[Nmax];
double sol_x,sol_y;
int N;
void read_data()
{
    FILE*f = fopen("adapost2.in", "r");
    fscanf(f,"%d",&N);

    for(int i=1;i<=N;++i)
        fscanf(f,"%lf%lf", &X[i],&Y[i]);
    fclose(f);
}
double dist(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2) + (y1-y2) * (y1-y2));
}
double total_dist(double x, double y)
{
    double res = 0.0f;
    for(int i=1;i<=N;++i)
        res += dist(x,y, X[i], Y[i]);
    return res;
}
void solve()
{
    //G
    double x=0.0f,y=0.0f;
    for(int i=1;i<=N;++i)
    {
        x += X[i];
        y += Y[i];
    }
    x/= (double)N;
    y/= (double)N;

    double eps = 0.001;
    double step = 400.0f;
    double current_dist;
    while(step > eps)
    {
        current_dist = total_dist(x,y);
        if(current_dist > total_dist(x+step, y))
            x = x+step;
        else if(current_dist > total_dist(x-step,y))
            x = x-step;
        else if(current_dist > total_dist(x, y+step))
            y = y+step;
        else if(current_dist > total_dist(x, y-step))
            y -= step;
        else
            step *= 0.5f;
    }
    sol_x = x;
    sol_y = y;
}
void write()
{
    ofstream g("adapost2.out");
    g<<sol_x<<" "<<sol_y;
    g.close();
}
int main()
{
    read_data();
    solve();
    write();
    return 0;
}