Cod sursa(job #1059409)

Utilizator cdascaluDascalu Cristian cdascalu Data 16 decembrie 2013 17:38:34
Problema Adapost 2 Scor 21
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 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 50000
using namespace std;

vector< pair<float,float> > vec;
float sol_x,sol_y;
int N;
void read_data()
{
    FILE*f = fopen("adapost2.in", "r");
    fscanf(f,"%d",&N);

    float x,y;
    for(int i=1;i<=N;++i)
    {
        fscanf(f,"%f%f", &x,&y);
        vec.push_back(make_pair(x,y));
    }
    fclose(f);
}
float dist(float x1, float y1, float x2, float y2)
{
    return sqrt((x1-x2)*(x1-x2) + (y1-y2) * (y1-y2));
}
float total_dist(float x, float y)
{
    float res = 0.0f;
    for(int i=0;i<vec.size();++i)
        res += dist(x,y, vec[i].first, vec[i].second);
    return res;
}
void solve()
{
    //G
    float x=0.0f,y=0.0f;
    for(int i=0;i<vec.size();++i)
    {
        x += vec[i].first;
        y += vec[i].second;
    }
    x/= (float)N;
    y/= (float)N;

    float eps = 0.00001;
    float step = 400.0f;
    float 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;
}