Cod sursa(job #2067791)

Utilizator DawlauAndrei Blahovici Dawlau Data 16 noiembrie 2017 20:32:48
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<fstream>
#include<iomanip>
#include<cmath>
#include<climits>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
struct coords{
    double x,y;
};
const int NMAX=50005,moveX[]={1,-1,0,0},moveY[]={0,0,1,-1},INF=INT_MAX;
const double eps=0.00001;
coords points[NMAX],ans;
int n;
double min_dist=INF;
void read_data(){
    ios::sync_with_stdio(false);
    fin.tie(NULL);fout.tie(NULL);
    fin>>n;
    int i;
    for(i=1;i<=n;++i){
        fin>>points[i].x>>points[i].y;
        ans.x+=points[i].x;
        ans.y+=points[i].y;
    }
}
void setup_point(){
    ans.x/=(double)n;
    ans.y/=(double)n;
}
double distance(const coords &a,const coords &b){
    return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
double distance_to_all_points(const coords &auxPoint){
    int i;
    double dist=0;
    for(i=1;i<=n;++i)
        dist+=distance(points[i],auxPoint);
    return dist;
}
void search_point(){
    double cst=100.0,auxDist;
    int i;
    coords auxPoint;
    while(cst>=eps){
        for(i=0;i<4;++i){
            auxPoint.x=ans.x+moveX[i]*cst;
            auxPoint.y=ans.y+moveY[i]*cst;
            auxDist=distance_to_all_points(auxPoint);
            if(min_dist>auxDist){
                min_dist=auxDist;
                ans=auxPoint;
            }
        }
        cst/=2;
    }
}
int main(){
    read_data();
    setup_point();
    search_point();
    fout<<fixed<<setprecision(4)<<ans.x<<' '<<ans.y;
}