Pagini recente » Cod sursa (job #2135462) | Cod sursa (job #1583648) | Cod sursa (job #2703150) | Cod sursa (job #2401796) | Cod sursa (job #1998836)
#include <bits/stdc++.h>
using namespace std;
typedef double f64;
const int NMAX = 50005;
struct PTX {
f64 x, y;
inline PTX() { }
inline PTX(f64 _x, f64 _y) {
x = _x;
y = _y;
}
friend ifstream& operator >> (ifstream &fs, PTX &arg) {
fs>>arg.x>>arg.y;
return fs;
}
friend ofstream& operator << (ofstream &fs, PTX &arg) {
fs<<arg.x<<' '<<arg.y;
return fs;
}
};
int n;
PTX pts[NMAX];
inline f64 dist(const PTX &a, const PTX &b) {
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
inline f64 sdist(const PTX &arg) {
f64 sum = 0.;
for(int i=0; i<n; ++i)
sum+= dist(arg, pts[i]);
return sum;
}
int sx[] = {0, 1, -1, 0},
sy[] = {1, 0, 0, -1};
int main(void) {
ifstream fi("adapost2.in");
ofstream fo("adapost2.out");
bool flag;
PTX tmp, ant(500., 500.);
f64 cdt, tdt, p;
int lim;
fi>>n;
for(int i=0; i<n; ++i)
fi>>pts[i];
cdt = sdist(ant);
p = 256.;
lim = 38;
if(n<10000)
lim = 50;
for(int stp=0; stp<lim; ++stp) {
for(int i=0; i<4; ++i) {
tmp.x = ant.x + p * sx[i];
tmp.y = ant.y + p * sy[i];
tdt = sdist(tmp);
if(tdt < cdt) {
cdt = tdt;
ant = tmp;
p *= 2.;
break;
}
}
p/= 2;
}
fo<<ant<<'\n';
fi.close();
fo.close();
return 0;
}