Cod sursa(job #2783147)

Utilizator RamanujanNeacsu Mihnea Ramanujan Data 13 octombrie 2021 21:00:51
Problema Adapost 2 Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>
#define MAXN 50000
#define START_STEP 100
#define MAX_PRECISION 0.001
using namespace std;
pair<double, double> a[MAXN];
int n;
double distanceToSoldiers(double x, double y){
    double currDistance=0;//aici adunam distantele
    for(int i=0; i<n; i++){
       currDistance+=sqrt((x-a[i].first)*(x-a[i].first)+(y-a[i].second)*(y-a[i].second));//adaug diatanta intre cort si soldat
    }
    return currDistance;//da, e chiar atat de simplu
}
void annealToCenter(double &x, double &y){// pe astea le si intorc, ce sa ma-ncurc cu template-uri
    double step=START_STEP;//nu folosim numere magice pe-aici
    while(step>MAX_PRECISION){//vom tot scadea pasul
        double dx[]={-step, 0, step, 0};
        double dy[]={0, step, 0, -step};
        int pos=100;
        double dist=distanceToSoldiers(x, y);
        for(int i=0; i<4; i++){
            if(distanceToSoldiers(x+dx[i], y+dy[i])<dist){
                dist=distanceToSoldiers(x+dx[i], y+dy[i]);
                pos=i;
            }
        }
        if(pos==100){//daca m-am blocat, o iau cu binisorul
          step/=2;//va ras-scadea, ca ii double
        }
        else{//altfel, mut
            x+=dx[pos], y+=dy[pos];
        }
    }
}
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
int main()
{
    fin>>n;
    double sumX=0, sumY=0;
    for(int i=0; i<n; i++){
        fin>>a[i].first>>a[i].second;
        sumX+=a[i].first, sumY+=a[i].second;
    }
    sumX/=n, sumY/=n;
    annealToCenter(sumX, sumY);
    fout<<sumX<<" "<<sumY;
    return 0;
}