Pagini recente » Cod sursa (job #1864348) | Cod sursa (job #2163555) | Cod sursa (job #1121182) | Cod sursa (job #2207748) | Cod sursa (job #2067791)
#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;
}