Cod sursa(job #63543)

Utilizator coderninuHasna Robert coderninu Data 29 mai 2007 13:12:14
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>
#include <math.h>
#define infile "adapost2.in"
#define outfile "adapost2.out"
#define err 0.00001

int n, i, dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
float x[50000][2];
long double xx, yy, distmin, dis;

void readdata()
{
 FILE *fin=fopen(infile, "r");
 fscanf(fin, "%d\n", &n);
 for (i=0; i<n; i++) fscanf(fin, "%f %f\n", &x[i][0], &x[i][1]);
 fclose(fin);
}

float dist(float x1, float y1, float x2, float y2)
{
 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void solve()
{
 for (i=0; i<n; i++)
     {
      xx+=x[i][0];
      yy+=x[i][1];
     }
 xx/=n;
 yy/=n;
 for (i=0; i<n; i++) distmin+=dist(xx,yy,x[i][0],x[i][1]);
 float marj=500;
 while (marj>err)
     {
      for (int dir=0; dir<4; dir++)
	  {
	   dis=0;
	   for (i=0; i<n; i++) dis+=dist(xx+dx[dir]*marj,yy+dy[dir]*marj,x[i][0],x[i][1]);
	   if (dis<distmin)
	       {
		xx+=dx[dir]*marj;
		yy+=dy[dir]*marj;
		distmin=dis;
	       }
	  }
      marj/=1.5;
     }
}

void writedata()
{
 float r1=xx, r2=yy;
 FILE *fout=fopen(outfile, "w");
 fprintf(fout, "%.4f %.4f", r1, r2);
 fclose(fout);
}

int main()
{
 readdata();
 solve();
 writedata();
 return 0;
}