Cod sursa(job #293000)

Utilizator gigi_becaliGigi Becali gigi_becali Data 31 martie 2009 21:06:38
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#define dim 8192

using namespace std;


char ax[dim];
int pz;

inline void cit(int &x)
{
	x=0;
	while(ax[pz] < '0' && ax[pz] > '9')
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	
	while(ax[pz] >= '0' && ax[pz] <= '9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	}
}

struct nod {int x, y;};

nod a[3001];
int n;
struct edge{ short i, j; int c;};

struct cmp
{
	bool operator()(const edge &a, const edge &b)const
	{
		if(a.c < b.c) return 1;
		return 0;
	}
};

edge E[6001];
edge apm[6001];
edge B[6001];
int M;
int t[3001];

inline int find(int i)
{
	if(i != t[i]) t[i]=find(t[i]);
	return t[i];
}

inline bool uneste(int i, int j)
{
	i=find(i);
	j=find(j);
	if(i == j) return 0;
	t[i]=j;
	return 1;
}


inline int distanta(nod a, nod b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
	
inline void rad(int n,int byte,edge a[], edge b[])
{
	int cnt[1024], ind[1024],i;
	memset(cnt, 0, sizeof(cnt));
	for(i=1; i <= n; ++i) ++cnt[(a[i].c>>byte)&1023];
	
	ind[0]=1;
	for(i=1; i < 1024; ++i) ind[i]=ind[i-1]+cnt[i-1];
	
	for(i=1; i <= n; ++i) b[ind[(a[i].c>>byte)& 1023]++]=a[i];
	
}


inline void radix(int n, edge A[])
{
	rad(n, 0, A, B);
	rad(n, 10, B, A);
	rad(n, 20, A, B);
	//rad(n, 30, B, A);
	for(int i=1; i <= n; ++i) A[i]=B[i];
}

void solve()
{//printf("__%d\n", M);
	radix(M, E);
	//sort(E+1, E+M+1,cmp());
int nr=0, i;
	//for(i=1; i <= M; ++i) printf("%d %d %d\n", E[i].i, E[i].j, E[i].c);
	
	//int sol=0;
	for(i=1; i <= M; ++i)
		if(uneste(E[i].i, E[i].j))
		{	apm[++nr]=E[i];
			//sol += E[i].c;
		}
		
//printf("%d\n", sol);
	for(i=1; i <= nr; ++i) E[i]=apm[i];
	M=nr;
	
	
	//printf("\n\n");
	
}

void init()
{
	//srand(time(0));
	
	n=2000;
	for(int i=1; i <= n; ++i) a[i].x=rand()%30000, a[i].y=rand()%30000;
}

int main()
{
	double ss=clock();
	//freopen("cablaj.in","r",stdin);
	
	//cit(n);
	
	init();
	
	//scanf("%d\n", &n);
	//printf("%d\n", n);
	//cit(a[1].x); cit(a[1].y);
	//scanf("%d %d\n", &a[1].x, &a[1].y);
	//scanf("%d %d\n", &a[2].x, &a[2].y);
	
	E[++M].i=1, E[M].j=2, E[M].c=distanta(a[1],a[2]);
	int j,i;
	
	for(i=3; i <= n; ++i)
	{
		//cit(a[i].x); cit(a[i].y);
		//scanf("%d %d\n", &a[i].x, &a[i].y);
		
		
		for(j=1;j < i; ++j)
			E[++M].i=j, E[M].j=i, E[M].c=distanta(a[i], a[j]);
		
		for(j=1; j <= i; ++j) t[j]=j;
		
		solve();
		
	}
	
	double s=0;
	
	for(i=1; i <= M; ++i) s+=(double) sqrt((double)E[i].c);
	
	printf("%.3lf\n",s); 
	
	fprintf(stderr,"Time:%lf\n", (clock()-ss)/(double)CLOCKS_PER_SEC);
	return 0;
}