Mai intai trebuie sa te autentifici.
Cod sursa(job #1118286)
Utilizator | Data | 24 februarie 2014 09:39:06 | |
---|---|---|---|
Problema | Adapost 2 | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.49 kb |
#include <fstream>
#include <cmath>
#include <iomanip>
#define in "adapost2.in"
#define out "adapost2.out"
#define Max_Size 50009
#define eps 0.001
typedef std :: pair < double, double > POINT;
std :: ifstream f(in);
std :: ofstream g(out);
int N;
POINT CG, A[Max_Size];
double best_sol;
short dx[] = {-1, 0, 0, 1};
short dy[] = {0, -1, 1, 0};
inline void Read_Data() {
f >> N;
for(int i = 1; i <= N; ++i) {
f >> A[i].first >> A[i].second;
CG.first += A[i].first, CG.second += A[i].second;
}
CG.first /= N, CG.second /= N;
}
inline double Count_Dist(POINT p) {
double d = 0;
for(int i = 1; i <= N; ++i)
d += sqrt((p.first - A[i].first) * (p.first - A[i].first) + (p.second - A[i].second) * (p.second - A[i].second));
return d;
}
inline void Solve() {
best_sol = Count_Dist(CG);
double d; POINT new_point;
for(double i = 100; i >= eps; i /= 2) {
bool ok = 1;
while(ok) {
ok = 0;
for(int k = 0; k < 4; ++k) {
new_point.first = CG.first + i * dx[k];
new_point.second = CG.second + i * dy[k];
d = Count_Dist(new_point);
if(d < best_sol) {
best_sol = d;
CG = new_point;
ok = 1;
}
}
}
}
}
int main() {
Read_Data();
Solve();
g << std :: fixed << std :: setprecision(4) << CG.first << ' ' << CG.second << '\n';
g.close();
return 0;
}