Pagini recente » cnitv_baraj_1 | *PAGINA LUI VI$$U* | Monitorul de evaluare | Transport | Cod sursa (job #1874764)
// TEAM CORNELL
#include<bits/stdc++.h>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef pair<double,double> pdd;
#define eps 0.0001
ll N;
#define Nmax 1010100
vector<pdd> v;
double dist(pdd &a, pdd &b) {
return sqrt((1.0*a.fs-b.fs) *(1.0*a.fs-b.fs) + (1.0*a.sc - b.sc) * (1.0*a.sc-b.sc));
}
double getdist(pdd x) {
double ret = 0;
for(auto a : v) {
ret += dist(a,x);
}
return ret;
}
int T=0;
map<double,int> h;
int main() {
freopen("adapost2.in","r",stdin);
freopen("adapost2.out","w",stdout);
cin.sync_with_stdio(false);
// cin >> T;
T=1;
while(T--) {
v.clear();
double start = 1;
while(start < 10000000) start *= 2;
pdd cur=mp(0,0);
scanf("%d",&N);
for(int i=0;i<N;++i) {
double a,b;
scanf("%lf%lf",&a,&b);
cur.fs += a;
cur.sc += b;
v.pb(mp(a,b));
}
// cout << v.size() << endl;
//cout << v.size() << endl;
cur.fs /= N;
cur.sc /= N;
//cout << v.size() << endl;
double curd = getdist(cur);
int NRQ = 0;
while(start > eps) {
int ok = 0;
double curd = getdist(cur);
double r = getdist(mp(cur.fs+start,cur.sc));
double l = getdist(mp(cur.fs-start,cur.sc));
double d = getdist(mp(cur.fs,cur.sc-start));
double u = getdist(mp(cur.fs,cur.sc+start));
if(r < curd && u > curd && d > curd) {
cur = mp(cur.fs+start,cur.sc);
continue;
}
if(l < curd && u > curd && d > curd) {
cur = mp(cur.fs-start,cur.sc);
continue;
}
if(u < curd && l > curd && r > curd) {
cur = mp(cur.fs,cur.sc+start);
continue;
}
if(d < curd && l > curd && r > curd) {
cur = mp(cur.fs,cur.sc-start);
continue;
}
if(d <curd && l < curd) {
double d1 = (curd - d);
double d2 = (curd - l);
cur.fs -= d2 / (d1+d2) * start;
cur.sc -= d1 / (d1+d2) * start;
continue;
}
if(d <curd && r < curd) {
double d1 = (curd - d);
double d2 = (curd - r);
cur.fs += d2 / (d1+d2) * start;
cur.sc -= d1 / (d1+d2) * start;
continue;
}
if(u < curd && r < curd) {
double d1 = (curd - u);
double d2 = (curd - r);
cur.fs += d2 / (d1+d2) * start;
cur.sc += d1 / (d1+d2) * start;
continue;
}
if(u < curd && l < curd) {
double d1 = (curd - u);
double d2 = (curd - l);
cur.fs -= d2 / (d1+d2) * start;
cur.sc += d1 / (d1+d2) * start;
continue;
}
start = start / 2.0;
}
printf("%.12lf %.12lf\n",cur.fs, cur.sc);
}
}