Cod sursa(job #1438299)

Utilizator DEFINEtelyEngineersUPB Pirtoaca Vasilescu Zamfiratos DEFINEtelyEngineers Data 19 mai 2015 16:30:05
Problema Adapost 2 Scor 74
Compilator cpp Status done
Runda last_acm_practice Marime 1.14 kb
#include<iostream>
#include<fstream>
#include<math.h>
#include<iomanip>
using namespace std;

#define NMAX 500001

struct punct {
	double x,y;
};

punct v[NMAX];

double dx[]={0,-1.0,0.0,1.0,0.0};
double dy[]={0,0.0,1.0,0.0,-1.0};

double dist(punct a, punct b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double suma(punct a, int n)
{
	double s;
	int i;
	s=0;
	for(i=1;i<=n;i++)
		s=s+dist(a,v[i]);
	return s;
}

int main ()
{
	int n,i,j,ok;
	double step,value,d;
	punct sol,aux,pmin;
	ifstream f("adapost2.in");
	ofstream g("adapost2.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i].x>>v[i].y;
	f.close();
	sol.x=0;
	sol.y=0;
	for(i=1;i<=n;i++) {
		sol.x=sol.x+v[i].x;
		sol.y=sol.y+v[i].y;
	}
	sol.x=sol.x/n;
	sol.y=sol.y/n;
	step=1000.000;
	for(i=1;i<=25;i++) {
		value=suma(sol,n);
		pmin=sol;
		ok=1;
		for(j=1;j<=4;j++) {
			aux.x=sol.x+dx[j]*step;
			aux.y=sol.y+dy[j]*step;
			d=suma(aux,n);
			if(d<value) {
				value=d;
				pmin=aux;
				ok=0;
			}
		}
		if(ok)
			step=step/2;
		sol=pmin;
	}
	g<<fixed;
	g<<setprecision(4)<<sol.x<<" "<<sol.y;
	g.close();
	return 0;
}