OJ Board

Code: Select all

#include <stdio.h>
#include <math.h>

int main()
{
    int n,m;
    double a,b,x,y,rope;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        rope = 0;
        scanf("%d",&m);
        scanf("%lf%lf",&a,&b);
        for(int i = 1; i < m; i++)
        {
            scanf("%lf%lf",&x,&y);
            rope += sqrt(pow(x-a,2)+pow(y-b,2));
            a = x;b = y;
        }    
        printf("%.2lf\n\n",rope);
    }    
    return 0;
}    

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ERROR 0.00000001


#define MAXV 110
#define MAXDEGREE 110
#define MAXINT 2e15

long parent[MAXV+1];

typedef struct{
	double x;
	double y;
}POint;
POint point[102];



typedef struct{
	long v;
	double weight;
}edge;

typedef struct{
	edge edges[MAXV+1][MAXDEGREE];
	long degree[MAXV+1];
	long nvertices;
	long nedges;
}graph;


typedef struct{
	long x,y;
	double w;
}qedge;

typedef struct{
	qedge element[MAXV+1];
	long head;
	long tail;
}queue;


void initialize_graph(graph *g);
void insert_edge(graph *g,long x,long y,double w,bool directed);
double kruskal(graph *g);
qedge deque(queue *q);
void set_q(queue *q,graph *g);
int sortfunc(const void *a,const void *b);

double distance_between_point(double x1,double y1,double x2,double y2)
{
	return (  sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) )   );
}

void main()
{
	long i,j,test,n,start;
	double distance,cost=0,min;
	graph g;
	bool directed=false;
	
	
	scanf("%ld",&test);
	
	while(test--)
	{
		
		scanf("%ld",&n);
		
		for(i=0;i<n;i++)
			scanf("%lf %lf",&point[i].x,&point[i].y);
		
		min=MAXINT;
		initialize_graph(&g);
		
		g.nvertices = n;
		
		
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
			{
				distance = distance_between_point(point[i].x,point[i].y,point[j].x,point[j].y);
				insert_edge(&g,i+1,j+1,distance,directed);
				if(distance<min){
					min = distance;
					start = j+1;
				}
				
			}
		}
		
		/*
		printf("%ld\n",g.nedges);
		
		  for(i=1;i<=g.nedges;i++)
		  {
		  for(j=0;j<g.degree[i];j++)
		  printf("%ld %ld %lf\n",i,g.edges[i][j].v,g.edges[i][j].weight);
		  
			}
		*/		
		
		
		cost = kruskal(&g);
		
		
		printf("%.2lf\n",cost);
		if(test>0)
			printf("\n");
		
		
	}//while
}//main


void initialize_graph(graph *g)
{
	long i;
	g->nvertices=0;
	g->nedges=0;
	for(i=1;i<=MAXV;i++)
		g->degree[i]=0;
}

void insert_edge(graph *g,long x,long y,double w,bool directed)
{
	g->edges[x][g->degree[x]].v=y;
	g->edges[x][g->degree[x]].weight=w;
	g->degree[x]++;
	if(directed==false)
		insert_edge(g,y,x,w,true);
	else
		g->nedges++;
}




double kruskal(graph *g)
{
	queue q;
	qedge now,store[MAXV+1];
	long set[MAXV+1];
	long cnt=0;
	long i,tmp;
	
	double cost;
	
	for(i=0;i<=MAXV;i++)
		set[i]=i;
	set_q(&q,g);
	while(q.head<q.tail)
	{
		now=deque(&q);
		if(set[now.x]!=set[now.y])
		{
			store[cnt]=now;
			cnt++;
			tmp=set[now.y];
			for(i=0;i<=MAXV;i++)
			{
				if(set[i]==tmp)
					set[i]=set[now.x];
			}
		}
		if(cnt==g->nvertices-1)
			break;
	}
	cost=0;
	//printf("The edges of MST are :(Kruskal's algorithm evaluated)\n");
	for(i=0;i<cnt;i++)
	{
		//printf("%ld %ld %lf\n",store[i].x,store[i].y,store[i].w);
		cost+=store[i].w;
	}
	return cost;
	//printf("The total length of MST is : %lf\n",cost);
}

qedge deque(queue *q)
{
	qedge ed;
	ed=q->element[q->head];
	q->head++;
	return(ed);
}

void set_q(queue *q,graph *g)
{
	long i,j;
	for(i=0;i<=MAXV;i++)
		q->element[i].w=MAXINT;
	q->head=q->tail=0;
	for(i=1;i<=g->nvertices;i++)
	{
		for(j=0;j<g->degree[i];j++)
		{
			q->element[q->tail].x=i;
			q->element[q->tail].y=g->edges[i][j].v;
			q->element[q->tail].w=g->edges[i][j].weight;
			q->tail++;
		}
	}
	qsort(&q->element,q->tail,sizeof(qedge),sortfunc);
}

int sortfunc(const void *a,const void *b)
{
	qedge *x,*y;
	x=(qedge *)a;
	y=(qedge *)b;
	
	if (fabs(x->w-x->w)<ERROR)return 0;  
	if(x->w>y->w)
		return 1;
	if(x->w<y->w)
		return -1;
	
	return 0;
	
}

Code: Select all

#include<iostream>
#include<cmath>
#include<algorithm>
#include <iomanip>
using namespace std;
int rank[1000];
int p[1000];


struct node
{
       int s;
       int d;
       float w;
};

bool operator <(const node &x1,const node &x2)
{
     if(x1.w<x2.w)
     return true;
     
     return false;
}

void makeset(int x)
{
           p[x]=x;
           rank[x]=0;
     
}

int findset(int px)
{
     if(px!=p[px])
     return px=findset(p[px]);
     else
     return px;
}

void mergset(int px,int py)
{
     int x=findset(px);
     int y=findset(py);
     
     if(rank[x]>rank[y])
     p[y]=x;
     
     else
     p[x]=y;
     
     if(rank[x]==rank[y])
     rank[y]=rank[y]+1;
}

int main()
{
    int t;
    cin>>t;
    for(int k=0;k<t;k++)
    {
          
            int n;
            cin>>n;
            float ans=0.0;
            float a[1000][2];
            node x[1001];
           
            for(int i=0;i<n;i++)
            {
                    cin>>a[i][0]>>a[i][1]; 
            }
            int c=0;
           
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(i!=j)
                    {
                         float xx=a[i][0]-a[j][0];
                         float yy=a[i][1]-a[j][1];
                         
                         xx=xx*xx;
                         yy=yy*yy;
                         
                         xx=sqrt(xx+yy);
                           
                         x[c].s=i;
                         x[c].d=j;
                         x[c].w=xx;
                         c++;
                           
                    }
                }
           }
         
           for(int i=0;i<c;i++)
           makeset(i);
   
           sort(x,x+c);
           
   
           for(int i=0;i<c;i++)
           {
                   if(findset(x[i].s)!=findset(x[i].d))
                   {
                         ans+=x[i].w;
                         mergset(x[i].s,x[i].d);                           
                   }
            }
            if(k<t-1)
            printf("%.2lf\n\n",ans);
            else
            printf("%.2lf\n",ans);
   
   
    }
    
}