Pagini recente » Cod sursa (job #703275) | Cod sursa (job #2298272) | Cod sursa (job #2952780) | Cod sursa (job #612166) | Cod sursa (job #2548169)
#include <bits/stdc++.h>
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (double &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
double sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser fin("adapost2.in");
ofstream fout("adapost2.out");
const int DIM = 5e4 + 7;
pair <double, double> vec[DIM];
int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
double dist(double x1, double y1, double x2, double y2)
{
double ans = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
ans = sqrt(ans);
return ans;
}
void update(double &x, double &y, double cat, int n, double &best)
{
int it = -1;
for(int i = 0; i < 8; i++)
{
double nx = x + dx[i] * cat;
double ny = y + dy[i] * cat;
double act = 0;
for(int i = 1; i <= n; i++)
act += dist(nx, ny, vec[i].first, vec[i].second);
if(act < best)
{
best = act;
it = i;
}
}
if(it != -1)
{
x += dx[it] * cat;
y += dy[it] * cat;
}
}
main()
{
int n;
fin >> n;
double x = 0;
double y = 0;
double best = 0;
for(int i = 1; i <= n; i++)
{
fin >> vec[i].first >> vec[i].second;
x += vec[i].first;
y += vec[i].second;
}
x /= n;
y /= n;
for(int i = 1; i <= n; i++)
{
best += dist(x, y, vec[i].first, vec[i].second);
}
double cat = 1000;
for(int pas = 1; pas <= 30; pas++, cat /= 2)
{
update(x, y, cat, n, best);
}
fout << fixed << setprecision(7) << x << ' ' << y << '\n';
}