Pagini recente » Cod sursa (job #2571178) | Cod sursa (job #2167992) | Cod sursa (job #972526) | Cod sursa (job #1069767) | Cod sursa (job #2075461)
#include <iostream>
#include <fstream>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif
using namespace std;
ifstream in("adapost2.in");
ofstream out("adapost2.out");
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const int NMax = 5e4 + 5;
const int mod = 666013;
int N;
typedef pair<double,double> point;
point v[NMax];
point solve();
double getSum(point);
int main() {
in>>N;
for (int i=1;i <= N;++i) {
in>>v[i].first>>v[i].second;
}
point adapost = solve();
out<<fixed<<setprecision(6)<<adapost.first<<' '<<adapost.second<<'\n';
return 0;
}
point solve() {
point adapost = mp(0,0);
for (int i=1;i <= N;++i) {
adapost.first += v[i].first;
adapost.second += v[i].second;
}
adapost.first /= N;
adapost.second /= N;
double add = 100;
while (add > 1e-3) {
while (true) {
point top = mp(adapost.first,adapost.second + add),
bot = mp(adapost.first,adapost.second - add),
st = mp(adapost.first - add,adapost.second),
dr = mp(adapost.first + add,adapost.second);
double sumTop = getSum(top),
sumBot = getSum(bot),
sumSt = getSum(st),
sumDr = getSum(dr),
sumAdapost = getSum(adapost);
bool update = false;
if (sumTop < sumAdapost) {
sumAdapost = sumTop;
adapost = top;
update = true;
}
if (sumBot < sumAdapost) {
sumAdapost = sumBot;
adapost = bot;
update = true;
}
if (sumSt < sumAdapost) {
sumAdapost = sumSt;
adapost = st;
update = true;
}
if (sumDr < sumAdapost) {
sumAdapost = sumDr;
adapost = dr;
update = true;
}
if (!update) {
break;
}
}
add /= 2;
}
return adapost;
}
double getDist(point a,point b) {
double val = (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
return sqrt(val);
}
double getSum(point x) {
double ans = 0;
for (int i=1;i <= N;++i) {
ans += getDist(v[i],x);
}
return ans;
}