Pagini recente » Rating Karina Jafara (Jafarak) | Cod sursa (job #1986814) | Cod sursa (job #1203694) | Istoria paginii preoni-2006/finala/poze | Cod sursa (job #1516632)
#include <fstream>
#include <cmath>
using namespace std;
const int EPS = 0.001;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int NMAX = 50010;
struct point {double x, y;} v[NMAX];
int N;
double distance (point a, point b) {
return sqrt ( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}
double allDistanceSum (point Q) {
double ANS = 0;
for (int i = 1; i <= N; i++) {
ANS += distance (v[i], Q);
}
return ANS;
}
int main () {
ifstream fin ("adapost2.in");
ofstream fout ("adapost2.out");
point crt;
crt.x = crt.y = 0;
fin >> N;
for (int i = 1; i <= N; i++) {
fin >> v[i].x;
fin >> v[i].y;
crt.x += v[i].x;
crt.y += v[i].y;
}
crt.x /= N;
crt.y /= N;
double pas = 1000.0;
double distCrt = allDistanceSum (crt);
bool modif;
while (pas > EPS) {
modif = 0;
for (int i = 0; i < 4; i++) {
point tmp;
tmp.x = crt.x + dx[i] * pas;
tmp.y = crt.y + dy[i] * pas;
double distTmp = allDistanceSum (tmp);
if (distTmp < distCrt) {
distCrt = distTmp;
crt = tmp;
modif = 1;
}
}
if ( !modif) {
pas /= 2.0;
}
}
fout << crt.x << " " << crt.y << '\n';
return 0;
}