Pagini recente » Cod sursa (job #2648118) | Cod sursa (job #2316635) | Cod sursa (job #1843374) | Cod sursa (job #3248652) | Cod sursa (job #2083307)
#include<bits/stdc++.h>
using namespace std;
ifstream f("adapost2.in");
ofstream g("adapost2.out");
//structul pozitiei unui soldat
struct soldat{
double x;
double y;
};
int n;
double x,y,fort_x,fort_y;
//vector de soldati
vector<soldat>v(50005);
//calculeaza distanta intre 2 puncte
double dist(double x1, double y1, double x2, double y2){
return sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2 -y1));
}
//calculam suma distantelor soldatilor pana la fort
double dist_fort(double x, double y){
double sum_dist=0;
for (int i=1;i<=n;++i)
sum_dist+=dist(x,y,v[i].x,v[i].y);
return sum_dist;
}
int main(){
f>>n;
for (int i=1;i<=n;++i){
f>>x>>y;
v[i] = {x*1000.0,y*1000.0}; //pentru a nu pierde din precizie
fort_x+=v[i].x;
fort_y+=v[i].y;
}
//incepem cu pozitia medie dintre toate pozitiile
fort_x/=(double)n; fort_y/=(double)n;
//suma distantelor soldatilor pana la fort
//cu cat suma e mai mica cu atat fortule intr-o pozitie optima
double curr_dis=dist_fort(fort_x,fort_y);
//stabilim un pas cu care se modifica valorile ce pot fi mai bune
double pas=100000.000;
while (pas>=1){
//alegem 4 pozitii ce pot fi mai bune ca pozitia fortului
double dr=dist_fort(fort_x+pas,fort_y);
double st=dist_fort(fort_x-pas,fort_y);
double sus=dist_fort(fort_x,fort_y+pas);
double jos=dist_fort(fort_x,fort_y-pas);
//apoi le comparam si mutam fortul
if (dr<curr_dis){
curr_dis=dr;
fort_x+=pas;
}
else if (st<curr_dis){
curr_dis=st;
fort_x-=pas;
}
else if (sus<curr_dis){
curr_dis=sus;
fort_y+=pas;
}
else if (jos<curr_dis){
curr_dis=jos;
fort_y-=pas;
}
else
pas *= 0.4; //raportul cu care se modifica pasul daca nu s-au gasit pozitii mai bune
}
//reintoarcem numerele la precizia initiala
fort_x/=1000.0; fort_y/=1000.0;
g<<fort_x<<" "<<fort_y;
}