Pagini recente » Cod sursa (job #2340825) | Cod sursa (job #2718468) | Cod sursa (job #2665866) | Cod sursa (job #2826990) | Cod sursa (job #1073087)
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <iostream>
#define NMAX 50001
#define MAXDIST 1000000000
using namespace std;
class Punct {
private:
long double x, y;
public:
Punct(const long double &x_src = 0, const long double &y_src = 0): x(x_src), y(y_src) {}
long double distanceTo(const Punct &p) const {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
void setX(const long double &x_src){
x = x_src;
}
void setY(const long double &y_src) {
y = y_src;
}
long double getX() const {
return x;
}
long double getY() const {
return y;
}
};
int N;
vector<Punct> puncte;
Punct best;
void input() {
ifstream in("adapost2.in");
in >> N;
long double xG = 0, yG = 0;
for (int i = 0; i < N; ++i) {
long double x, y;
in >> x >> y;
xG += x, yG += y;
Punct p(x, y);
puncte.push_back(p);
}
xG /= N, yG /= N;
best.setX(xG);
best.setY(yG);
in.close();
}
inline long double squareDistanceToAll(const Punct &p) {
long double dist = 0;
for (int i = 0; i < N; ++i) {
dist += p.distanceTo(puncte[i]);
}
return dist;
}
Punct binSearch(long double dist, Punct p, long double current_dist) {
for (int i = 0; i < 25; ++i) {//while (dist >= 0.001)
Punct up(p.getX(), p.getY() + dist);
Punct down(p.getX(), p.getY() - dist);
Punct left(p.getX() - dist, p.getY());
Punct right(p.getX() + dist, p.getY());
long double up_dist = squareDistanceToAll(up);
long double down_dist = squareDistanceToAll(down);
long double left_dist = squareDistanceToAll(left);
long double right_dist = squareDistanceToAll(right);
long double min_dist = MAXDIST;
if (up_dist < min_dist) {
best = up;
min_dist = up_dist;
}
if (down_dist < min_dist) {
best = down;
min_dist = down_dist;
}
if (left_dist < min_dist) {
best = left;
min_dist = left_dist;
}
if (right_dist < min_dist) {
best = right;
min_dist = right_dist;
}
if (min_dist < current_dist) {
p = best;
current_dist = min_dist;
}
dist /= 2.0;
}
return p;
}
void solve() {
best = binSearch(2048 * 2, best, squareDistanceToAll(best));
}
inline void output() {
ofstream out("adapost2.out");
out << setprecision(10) << best.getX() << " " << best.getY();
out.close();
}
int main() {
input();
solve();
output();
return 0;
}