Pagini recente » Cod sursa (job #1259129) | Cod sursa (job #2902458) | Cod sursa (job #1853743) | Cod sursa (job #988047) | Cod sursa (job #956075)
Cod sursa(job #956075)
#include <cstdio>
#include <utility>
#include <cmath>
using namespace std;
#define x first
#define y second
#define mp make_pair
typedef pair<float,float> point;
const int MAX_N = 50100;
const float EPS = 0.001;
point v[MAX_N];
float SX,SY;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
int n;
inline float dist(const point &A,const point &B)
{
float delX,delY;
delX = A.x - B.x;
delY = A.y - B.y;
delX *= delX;
delY *= delY;
return sqrt(delX+delY);
}
inline float total_dist(const point &X)
{
float 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 = 1000;
bool changed;
int i;
while(step > EPS){
changed = 0;
float original = total_dist(P);
float posib;
for(i = 0 ; i < 4 ; ++ i){
consider = mp( P.x + step * dx[i],P.y + step * dy[i] );
posib = total_dist(consider);
if( posib < original){
changed = 1;
P = consider;
break;
}
}
if(!changed)
step /= 2.0;
}
printf("%f %f\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("%f %f",&v[i].x,&v[i].y);
SX += v[i].x;
SY += v[i].y;
}
SX /= n;
SY /= n;
solve();
}