Pagini recente » Clasament Teme ACM Unibuc 2013 | Cod sursa (job #1054631)
#include <cstdio>
#include <math.h>
#include <iomanip>
#define maxxx 50010
FILE *fin,*gout ;
using namespace std;
int n;
double x[maxxx], y[maxxx];
double minn = 200000000;
double fun(int i, int j)
{
double x1 = x[i]-x[j], y1 = y[i] - y[j];
return sqrt( x1 * x1 + y1 * y1);
}
double lungime(double a, double b)
{
double s0 = 0;
x[n + 1] = a; y[n + 1] = b;
for( int i = 1; i <= n; i++)
s0 += fun(i, n+1);
return s0;
}
int main()
{
fin=fopen("adapost2.in","r");
gout=fopen("adapost2.out","w");
int i;
double sxx = 0, syy = 0,eroare = 200;
fscanf(fin,"%d",&n);
for( i = 1; i <= n; i++)
{
fscanf(fin,"%lf %lf",&x[i],&y[i]);
sxx += x[i];
syy += y[i];
}
sxx /= n;
syy /= n;
while(eroare > 0.0005)
{
double f;
f = lungime(sxx + eroare, syy);
if( f < minn)
{
minn = f;
sxx += eroare;
continue;
}
f = lungime(sxx - eroare, syy);
if( f < minn)
{
minn = f;
sxx -= eroare;
continue;
}
f = lungime( sxx, syy + eroare);
if( f < minn)
{
minn = f;
syy += eroare;
continue;
}
f = lungime( sxx, syy - eroare);
if( f < minn)
{
minn = f;
syy -= eroare;
continue;
}
eroare = eroare / 2;
}
fprintf(gout,"%4f %4f",sxx,syy);
return 0;
}