Cod sursa(job #193791)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 7 iunie 2008 10:10:37
Problema Adapost 2 Scor 23
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
#include<math.h>
float x,y,a[50005],b[50005];   
float Smin;   
long n;   
const float l[10]={-1,-1,-1,0,0,1,1,1};   
const float c[10]={-1,0,1,-1,1,-1,0,1};
void citire(){
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%f%f",&a[i],&b[i]);   
}
float ec(float a,float b,float x,float y){
	return sqrt((a-x)*(a-x) + (b-y)*(b-y));
}
void solv(){
	float d=1000;
	while (d>=0.00005){
		int ok=1;
		while (ok){
			ok=0;
			float x1=x,y1=y,S=0;
			for (int k=0;k<8;k++){
				S=0;
				for (int i=0;i<n;i++)
					S+=ec(x1+(float)l[k]*d,y1+(float)c[k]*d,a[i],b[i]);
				if(S<Smin){
					Smin=S;
					x=x1+(float)l[k]*d;
					y=y1+(float)c[k]*d;
					ok=1;
				}
			}
		}
		d/=2;
	}
}
int main (){ 
	int i;
	freopen("adapost2.in","r",stdin);
	freopen("adapost2.out","w",stdout);
	citire();
	Smin=1000000000;
	for(i=0;i<n;i++){
		x+=a[i];
		y+=b[i];
	}
	x/=n;
	y/=n;
	solv();
	printf("%.4f %.4f\n",x,y);
	fclose(stdin);
	fclose(stdout);
	return 0;
}