Pagini recente » Monitorul de evaluare | Clasament simularecls10_10 | Monitorul de evaluare | Cod sursa (job #2005540) | Cod sursa (job #2783147)
#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;
}