Cod sursa(job #197050)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 1 iulie 2008 04:44:05
Problema Adapost Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define NMAX 400

struct pct{double x,y;};
struct dist{double d;short s,a;};
pct s[NMAX],a[NMAX];//sold adap
double d[NMAX][NMAX];
dist v[NMAX*NMAX];
int n,n2;

int fcmp(const void*a,const void*b){
if(((dist*)a)->d<((dist*)b)->d) return 1;
else if(((dist*)a)->d>((dist*)b)->d) return -1;
	 else return 0;
}
int w[NMAX];

int main(){
freopen("adapost.in","r",stdin);
freopen("adapost.out","w",stdout);
scanf("%d",&n);
n2=n*n;
int i,j,k;
for(i=0;i<n;++i) scanf("%lf%lf",&s[i].x,&s[i].y);
for(i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
for(i=0;i<n;++i)
	for(j=0;j<n;++j)
		d[i][j]=sqrt((s[i].x-a[j].x)*(s[i].x-a[j].x)+
					 (s[i].y-a[j].y)*(s[i].y-a[j].y));
k=0;
for(i=0;i<n;++i)
	for(j=0;j<n;++j){
		v[k].d=d[i][j];
		v[k].s=i;
		v[k].a=j;
		k++;
		}
qsort(v,n2,sizeof(v[0]),fcmp);
double sd=0,dmax;
int start=0,sld;
for(i=0;i<n2;++i){
	sld=v[i].s;
	w[sld]++;
	if(w[sld]==n){
		if(!start) {start=1;dmax=v[i].d;}
		sd+=v[i].d;
		}
	}
printf("%0.3lf %0.3lf",dmax,sd);
return 0;
}