Pagini recente » Cod sursa (job #1856804) | Cod sursa (job #1039464) | Cod sursa (job #2753046) | Cod sursa (job #292206) | Cod sursa (job #1081640)
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <iostream>
#define NMAX 50001
#define MAXDIST 1000000000
using namespace std;
class Punct {
private:
double x, y;
public:
Punct(const double &x_src = 0, const double &y_src = 0): x(x_src), y(y_src) {}
double distanceTo(const Punct &p) const {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
void setX(const double &x_src){
x = x_src;
}
void setY(const double &y_src) {
y = y_src;
}
double getX() const {
return x;
}
double getY() const {
return y;
}
};
int N;
vector<Punct> puncte;
Punct best;
void input() {
ifstream in("adapost2.in");
in >> N;
double xG = 0, yG = 0;
for (int i = 0; i < N; ++i) {
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 double squareDistanceToAll(const Punct &p) {
double dist = 0;
for (int i = 0; i < N; ++i) {
dist += p.distanceTo(puncte[i]);
}
return dist;
}
Punct binSearch(double dist, Punct p, double current_dist) {
if (dist <= 0.0001) {
return p;
}
Punct right(p.getX() + dist, p.getY());
double right_dist = squareDistanceToAll(right);
if (current_dist - right_dist > 0.0001) {
return binSearch(dist, right, right_dist);
}
Punct left(p.getX() - dist, p.getY());
double left_dist = squareDistanceToAll(left);
if (current_dist - left_dist > 0.0001) {
return binSearch(dist, left, left_dist);
}
Punct down(p.getX(), p.getY() - dist);
double down_dist = squareDistanceToAll(down);
if (current_dist - down_dist > 0.0001) {
return binSearch(dist, down, down_dist);
}
Punct up(p.getX(), p.getY() + dist);
double up_dist = squareDistanceToAll(up);
if (current_dist - up_dist > 0.0001) {
return binSearch(dist, up, up_dist);
}
return binSearch(dist / 2.0, p, current_dist);
}
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;
}