Pagini recente » Cod sursa (job #95290) | Cod sursa (job #1300834) | Cod sursa (job #893754) | Cod sursa (job #2657053) | Cod sursa (job #1073086)
#include <fstream>
#include <vector>
#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 squareDistanceTo(const Punct &p) const {
return (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;
double maxX = 0, maxY = 0;
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;
maxX = max(maxX, x);
maxY = max(maxY, 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.squareDistanceTo(puncte[i]);
}
return dist;
}
Punct binSearch(double dist, Punct p, double current_dist) {
while (dist >= -0.001 && 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());
double up_dist = squareDistanceToAll(up);
double down_dist = squareDistanceToAll(down);
double left_dist = squareDistanceToAll(left);
double right_dist = squareDistanceToAll(right);
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;
}
return p;
}
void solve() {
Punct maxx(maxX, maxY);
best = binSearch(best.squareDistanceTo(maxx), best, squareDistanceToAll(best));
}
inline void output() {
ofstream out("adapost2.out");
out << best.getX() << " " << best.getY();
out.close();
}
int main() {
input();
solve();
output();
return 0;
}