Cod sursa(job #193792)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 7 iunie 2008 10:27:35
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 50005
double px[MAX],py[MAX];
const int dx[4]={-1,0,1,0};   
const int dy[4]={0,1,0,-1};
int N;
double x,y;
double funct(double pozx,double pozy){
    double rez=0;
    for (int i=0;i<N;i++){
        double dx,dy;
		dx=px[i]-pozx;
		dy=py[i]-pozy;
		rez+= sqrt(dx*dx + dy*dy);
	}
	return rez;
}
void solve(){
    double d=funct(x,y);
    double pas=100;
    while(pas>0.0004){
        int ok=0;
        for(int i=0;i<4;i++){
            double new_x=x+(double)pas*dx[i];
            double new_y=y+(double)pas*dy[i];
            double aux=funct(new_x,new_y);
            if(aux<d){
                d=aux;
                ok=1;   
                x=new_x;   
                y=new_y;   
                break;
            }
        }
        if(!ok)
            pas/=2;   
    }
}
int main(){
	int i;
    freopen("adapost2.in","r",stdin);   
    freopen("adapost2.out","w",stdout);
    scanf("%d\n",&N);
    for(i=0;i<N;i++){
        scanf("%lf %lf\n",&px[i],&py[i]);   
        x+=px[i];
		y+=py[i];   
    }
	x/=N;
	y/=N;
	solve();
	printf("%.4lf %.4lf\n",x,y);
	fclose(stdin);
    fclose(stdout);
    return 0;
}