Pagini recente » Cod sursa (job #325276) | Cod sursa (job #1422194) | Cod sursa (job #300465) | Cod sursa (job #536608) | Cod sursa (job #1967362)
#include <cstdio>
#include <cmath>
typedef double f64;
const int MAX_N = 50000;
const f64 EPS = 1e-4f;
f64 x[MAX_N], y[MAX_N];
inline f64 dist(f64 x1, f64 y1, f64 x2, f64 y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
inline f64 sumDist(f64 x1, f64 y1, int n) {
f64 s = 0.0f;
for(int i = 0; i < n; ++i)
s = s + dist(x1, y1, x[i], y[i]);
return s;
}
inline f64 best(f64 xRez, int n, f64 &sum) {
f64 yst = 0.0f, ydr = 1000.0f + EPS;
while(ydr - yst > EPS) {
f64 mid = (yst + ydr) / 2.0f;
f64 delta = sumDist(xRez, mid, n) - sumDist(xRez, mid + EPS, n);
if(delta >= 0.0f)
yst = mid;
else
ydr = mid;
}
sum = sumDist(xRez, yst, n);
return yst;
}
int main() {
int n;
FILE *fin = fopen("adapost2.in", "r");
fscanf(fin, "%d", &n);
for(int i = 0; i < n; ++i)
fscanf(fin, "%lf%lf", &x[i], &y[i]);
fclose(fin);
f64 xst = 0.0f, xdr = 1000.0f + EPS, y1, y2, s1, s2;
while(xdr - xst > EPS) {
f64 mid = (xdr + xst) / 2.0f;
best(mid, n, s1);
best(mid + EPS, n, s2);
f64 delta = s1 - s2;
if(delta >= 0.0f)
xst = mid;
else
xdr = mid;
}
FILE *fout = fopen("adapost2.out", "w");
fprintf(fout, "%f %f", xst, best(xst, n, s1));
fclose(fout);
return 0;
}