Pagini recente » Cod sursa (job #894244) | Cod sursa (job #2055592) | Cod sursa (job #704715) | Cod sursa (job #418959) | Cod sursa (job #956078)
Cod sursa(job #956078)
#include <cstdio>
#include <utility>
#include <cmath>
using namespace std;
#define x first
#define y second
#define mp make_pair
typedef pair<double,double> point;
const int MAX_N = 50100;
const double EPS = 0.0005;
point v[MAX_N];
double SX,SY;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
int n;
inline double dist(const point &A,const point &B)
{
double delX,delY;
delX = A.x - B.x;
delY = A.y - B.y;
delX *= delX;
delY *= delY;
return sqrt(delX+delY);
}
inline double total_dist(const point &X)
{
double ret = 0;
for(int i = 1 ; i <= n ; ++ i)
ret += dist(X,v[i]);
return ret;
}
void solve()
{
point P = mp(SX,SY);
point consider;
float step = 512;
bool changed;
double best_so_far = total_dist(P);
double posib;
int i;
while(step > EPS){
changed = 0;
for(i = 0 ; i < 4 ; ++ i){
consider = mp( P.x + step * dx[i],P.y + step * dy[i] );
posib = total_dist(consider);
if( posib < best_so_far){
changed = 1;
P = consider;
best_so_far = posib;
break;
}
}
if(!changed)
step /= 2.0;
}
printf("%lf %lf\n",P.x,P.y);
}
int main()
{
freopen("adapost2.in","r",stdin);
freopen("adapost2.out","w",stdout);
int i;
scanf("%d",&n);
for(i = 1 ; i <= n ; ++ i){
scanf("%lf %lf",&v[i].x,&v[i].y);
SX += v[i].x;
SY += v[i].y;
}
SX /= n;
SY /= n;
solve();
}