Pagini recente » Cod sursa (job #1028862) | Cod sursa (job #990737) | Cod sursa (job #1632417) | Cod sursa (job #1112581) | Cod sursa (job #1071021)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<fstream>
#include<iomanip>
using namespace std;
const int MAX_N = 50000 + 5;
const double MAX_PAS = 16.0;
const double EPS_PAS = 0.0001;
const double EPS = 0.00000001;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
class PointXY {
public:
double x, y;
PointXY() { x = y = 0.0; }
PointXY(double xx, double yy) { x = xx; y = yy; }
inline double operator*(const PointXY &other) const {
return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
}
};
int n;
PointXY points[MAX_N];
double cost(const PointXY &point) {
double answer=0.0;
for(int i = 1; i <= n; ++i) {
answer += point * points[i];
}
return answer;
}
int main() {
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
PointXY answer(0,0),next_answer;
fin >> n;
for(int i = 1; i <= n; ++i) {
fin >> points[i].x >> points[i].y;
answer.x += points[i].x;
answer.y += points[i].y;
}
answer.x /= n;
answer.y /= n;
double current_best_cost = cost(answer), current_cost;
for(double pas = MAX_PAS; pas >= EPS_PAS; pas *= 0.5) {
bool increase_pas=false;
for(int d = 0; d < 4; ++d) {
next_answer.x = answer.x + pas * dx[d];
next_answer.y = answer.y + pas * dy[d];
current_cost=cost(next_answer);
if(current_best_cost - current_cost >= EPS) {
current_best_cost = current_cost;
answer = next_answer;
increase_pas = true;
}
}
if(increase_pas) {
pas *= 2.0;
}
}
fout << setprecision(4) << fixed;
fout << answer.x << " " << answer.y << endl;
return 0;
}