Pagini recente » Cod sursa (job #1615067) | Cod sursa (job #1556340) | Cod sursa (job #2467247) | Cod sursa (job #1272241) | Cod sursa (job #1696502)
#include <fstream>
#include <cmath>
#include <iomanip>
#define Pe pair <double, double>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int MaxN = 50005;
const double Eps = 1e-4;
ifstream cin("adapost2.in");
ofstream cout("adapost2.out");
Pe pnt[MaxN], CurrPnt;
double dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
int n;
double CurrSum, BestSum;
inline double Dist(const Pe &a, const Pe &b) {
return sqrt((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}
inline double Check(const Pe &CandPnt) {
double ans = 0;
for (int i = 1; i <= n; ++i) {
ans += Dist(pnt[i], CandPnt);
}
return ans;
}
inline bool InBound(Pe CandPnt, const int &direction, const double &step) {
CandPnt.fi += dir[direction][0] * step;
CandPnt.se += dir[direction][1] * step;
bool InBoundFi = (CandPnt.fi <= 1000 and CandPnt.fi >= 1);
bool InBoundSe = (CandPnt.se <= 1000 and CandPnt.se >= 1);
return InBoundFi and InBoundSe;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> pnt[i].fi >> pnt[i].se;
}
CurrPnt = mp(1, 1);
CurrSum = Check(CurrPnt);
for(int iteration = 1; iteration <= 40; ++iteration) {
Pe BestPnt = CurrPnt;
int BestDir = -1;
BestSum = Check(CurrPnt);
CurrSum = BestSum;
for (int i = 0; i < 4; ++i) {
Pe NewPnt;
NewPnt.fi = CurrPnt.fi + dir[i][0] * Eps;
NewPnt.se = CurrPnt.se + dir[i][1] * Eps;
double NewSum = Check(NewPnt);
if (NewSum < BestSum) {
BestDir = i;
BestSum = NewSum;
}
}
double step = 100;
BestPnt.fi = CurrPnt.fi + dir[BestDir][0] * step;
BestPnt.se = CurrPnt.se + dir[BestDir][1] * step;
BestSum = Check(BestPnt);
while ((!InBound(CurrPnt, BestDir, step) or step > Eps) and CurrSum < BestSum) {
step /= 2;
BestPnt.fi = CurrPnt.fi + dir[BestDir][0] * step;
BestPnt.se = CurrPnt.se + dir[BestDir][1] * step;
BestSum = Check(BestPnt);
}
CurrPnt = BestPnt;
}
//}while (BestSum < CurrSum);
cout << fixed << setprecision(4) << CurrPnt.fi << ' ' << CurrPnt.se << '\n';
return 0;
}