Pagini recente » Cod sursa (job #205349) | Cod sursa (job #1019631) | Cod sursa (job #466839) | Cod sursa (job #1788601) | Cod sursa (job #2067151)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream in("adapost2.in");
ofstream out("adapost2.out");
#define ll long long
#define ull unsigned long long
#define pb push_back
const int NMax = 5e4 + 5;
const int sqMax = 320 + 5;
int N;
typedef pair<double,double> point;
point p[NMax];
double getDist(point a,point b);
double getSum(point x);
point solve();
int main() {
in>>N;
for (int i=1;i <= N;++i) {
in>>p[i].first>>p[i].second;
}
point adapost = solve();
out<<fixed<<setprecision(4)<<adapost.first<<' '<<adapost.second;
in.close();out.close();
return 0;
}
point solve() {
point adapost = point(0,0);
for (int i=1;i <= N;++i) {
adapost.first += p[i].first;
adapost.second += p[i].second;
}
adapost.first /= N;
adapost.second /= N;
double add = 100;
while (add > 1e-4) {
while (true) {
point pTop = point(adapost.first,adapost.second + add);
point pBot = point(adapost.first,adapost.second - add);
point pLeft = point(adapost.first - add,adapost.second);
point pRight = point(adapost.first + add,adapost.second);
double sumTop = getSum(pTop), sumBot = getSum(pBot),
sumLeft = getSum(pLeft), sumRight = getSum(pRight);
double mn = min(min(sumTop,sumBot),min(sumLeft,sumRight));
point minPoint;
if (mn == sumTop) {
minPoint = pTop;
}
else if (mn == sumBot) {
minPoint = pBot;
}
else if (mn == sumLeft) {
minPoint = pLeft;
}
else {
minPoint = pRight;
}
if (mn >= getSum(adapost)) {
break;
}
else {
adapost = minPoint;
}
}
add /= 2;
}
return adapost;
}
double getSum(point a) {
double ret = 0;
for (int i=1;i <= N;++i) {
ret += getDist(a,p[i]);
}
return ret;
}
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);
}