## 10034 - Freckles

Moderator: Board moderators

thanks for reply, Grinder, but that's not the problem...
i have make stupid mistake at the part u point..

i compare set[k] with set[e[j].v2] but value of set[e[j].v2] will change in the loop..
b3yours3lf
New poster

Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

### 10034 "Problem A: Freckles" Input/Output & WA

I recode this code

I have this code

[cpp]
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;

/* Tipos */

struct EdgeOfGraph {
int vertex1,vertex2;
float weight;
};

typedef EdgeOfGraph edge;

typedef struct tipo{
float x;
float y;
}tipo;
typedef vector<tipo>punto;

/* Variables globales */

edge *edges,*edgesOfTree;
int v1,v2,nEdges,nVertices,*set;

punto puntos(101); //hay numero de puntos maximo de 100 el 0 no lo utilizo
int numeropuntos=0;

/* Make Set */
void Make_set(int set[])
{
int ctr1;
for(ctr1=1;ctr1<=set[0];ctr1++)
set[ctr1]=ctr1;
};

{
int ctr1,ctr2,prevVal;
if(set[x1]==set[x2]) return ;
if(set[x1]<set[x2])
{prevVal=set[x2];
set[x2]=set[x1];
for(ctr1=1;ctr1<=set[0];ctr1++)
if(set[ctr1]==prevVal) set[ctr1]=set[x2];
return ;
}
if(set[x2]<set[x1])
{prevVal=set[x1];
set[x1]=set[x2];
for(ctr1=1;ctr1<=set[0];ctr1++)
if(set[ctr1]==prevVal) set[ctr1]=set[x1];
return ;
}
}

float distancia(float x1,float y1, float x2, float y2){
return ((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

void get_Edges(){

int ctrl=1;
int vertice1=1;
int vertice2=2;

while (ctrl<=nEdges){
while (vertice2<=numeropuntos){
edges[ctrl].vertex1=vertice1;
edges[ctrl].vertex2=vertice2;
edges[ctrl].weight=distancia(puntos[vertice1].x,puntos[vertice1].y,puntos[vertice2].x,puntos[vertice2].y);
vertice2++;
ctrl++;
}

vertice1++;
vertice2=vertice1+1;
}

}

/* Sort Edges */
void sort_Edges(edge edges[])
{
int ctr1,ctr2,ctr3;
edge temp;
for(ctr1=2;ctr1<=nEdges;ctr1++)
{
temp=edges[ctr1];
ctr2=ctr1;
while(ctr2>1 && temp.weight<edges[ctr2-1].weight)
{edges[ctr2]=edges[ctr2-1];
ctr2--;
};
if(ctr2!=ctr1)
edges[ctr2]=temp;
}
}

/* Kruskal */

void implementKruskal(edge edges[],edge edgesOfTree[],int set[])
{int ctr1,ctr2=1;
for(ctr1=1;ctr1<=edges[0].vertex1;ctr1++)
{if(set[edges[ctr1].vertex1]!=set[edges[ctr1].vertex2])
{
edgesOfTree[ctr2++]=edges[ctr1];
};
}
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=ctr2-1;
}

/* Recorremos los arcos sumando el resultado */
float salida=0;
int i;

for (i=1;i<=edgesOfTree[0].vertex1;i++){
salida+=sqrt(edges[i].weight);
}
printf("%.2lf\n",salida);
}

/* Ejecucion Kruskal */

int Kruskal(int nNodos)
{

set=(int *)malloc(sizeof(int) * (nNodos+1));
nEdges=nNodos*(nNodos -1)/2; //Maximo numero de nodos

edges=(edge *)malloc(sizeof(edge) * (nEdges+1));
edgesOfTree=(edge *)malloc(sizeof(edge) * (nEdges+1));

edges[0].vertex1=edges[0].vertex2=edges[0].weight=nEdges;
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=nEdges;

// Carga las aristas
get_Edges();

// Ordena
sort_Edges(edges);

// Preparo el set
set[0]=nNodos;
Make_set(set);

// Ejecuto kruskal
implementKruskal(edges,edgesOfTree,set);

return 0;
}

/* A partir de aqui se acaba kruskal */

float distancia_minima(int indice){
float min=100000000;
float temp=100000000;
int i;

for(i=indice+1;i<numeropuntos;i++){

temp=distancia(puntos[indice].x,puntos[indice].y,puntos[i].x,puntos[i].y);
//cout<<"temp es:"<<temp<<endl;
if (temp<min){min=temp;}
}

return min;
}

int main(int argc, char *argv[])
{
int numerotest=0;
int i=0;
float x,y;
float salida=0;

// 200 es el tama
Last edited by jandujar on Wed Mar 10, 2004 8:25 am, edited 1 time in total.
jandujar
New poster

Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

It seems that you have used the proper algorithm( Kruskal), but your code is far too long. I think you are considering extra things which is not required. For example, there is no need to define your own sort function, when a built in one is available.

Another thing, I have noticed in your code is you are passing parameters to the main function, which although not wrong, but is unnecessary.

You are also using dynamic memory allocation at various places, this is redundand. Since the number of points is given in advance, just use static array.

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

### I still need help

Thank, I know the code isn't acurancy. (I will recode when it's necessary)

I have got a "kruskal" algorithm and then I have recode it.

Seems that works , but always give me Wrong Answer. Why?
jandujar
New poster

Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

You can replace float by double.(infact all)
You wrote:

float salida=0;
int i;

for (i=1;i<=edgesOfTree[0].vertex1;i++){
salida+=sqrt(edges[i].weight);
}
printf("%.2lf\n",salida);
}
cuii e

alu_mathics
Learning poster

Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong

### Float -> Double

I tried with all floats to doubles and don't work.
Thanks

Any other suggest?
jandujar
New poster

Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### I think the problem is output

I Think the problem is output.

I write:

while(numtests>0)

cout<<number whith 2 decimal precition (redonded, shall i try truncated?)
cout<<endl;

end while

Is this correct?
jandujar
New poster

Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### INPUT/OUTPUT example

I have this input:
[cpp]
10

2
1.4 0.4
1.0 0.3

1
3.4 5.0

10
4.2 1.6
0.3 4.6
6.2 0.0
8.9 6.8
3.9 6.7
6.0 3.3
9.7 7.4
1.5 0.7
6.5 8.9
2.1 3.0

1
6.6 7.3

9
8.0 3.2
0.9 9.7
6.8 7.6
8.9 2.1
9.6 6.0
8.6 6.2
6.4 9.1
5.0 8.8
3.1 1.8

9
4.0 7.7
4.4 1.7
8.3 2.0
1.8 8.2
2.8 7.0
2.4 2.2
4.4 0.1
7.9 2.4
7.3 6.2

2
0.6 4.0
9.1 8.5

6
8.0 3.4
7.7 5.4
7.7 4.6
9.9 0.3
8.7 6.9
3.4 1.6

1
6.7 7.5

4
9.1 0.8
8.0 9.0
9.0 9.1
7.5 5.1

[/cpp]

And this output

[cpp]
0.41

0.00

22.69

0.00

16.15

15.90

9.62

8.37

0.00

9.21
[/cpp]

Is this correct? Thanks

Nota: I use this program to generate inputs.

[cpp]
#include <iostream.h>
#include <time.h>
#include <stdlib.h>

void puntorandom(){
int input1, input2;

input1 = rand() * 10 / (RAND_MAX + 1);
input2 = rand() * 10 / (RAND_MAX + 1);

cout<<input1<<"."<<input2;
}

int main()
{
int puntos,i,j;
srand(time(NULL));

cout<<10<<endl<<endl;

for (i=0; i<10 ; i++)
{
puntos= rand() * 10 / (RAND_MAX + 1) +1;
cout<<puntos<<endl;
for (j=0;j<puntos;j++){

puntorandom();
cout<<" ";
puntorandom();
cout<<endl;
}
cout<<endl;

}
}
[/cpp]
jandujar
New poster

Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

jandujar, my acepted program prints the following output for your given input:
Code: Select all
`0.410.0023.940.0020.0618.229.6212.420.009.52`
Subeen
Experienced poster

Posts: 127
Joined: Tue Nov 06, 2001 2:00 am

Thanks Subeen!!!

So, my code is incorrect (only works in some cases!!!!)
jandujar
New poster

Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### Finaly I Did it

Thanks to Subeen your output save me.

Finally I implement Prim's Algorithm but i hava "Presentation Errors"

Basicaly I do.

[cpp]
While (num--){
...
...

printf("%.2lf\n\n",salida);

}

[/cpp]

with

[cpp]
While (num--){
...
...

printf("%.2lf\n",salida);
if (num>0){
cout<<endl;
}

}

[/cpp]

I tried too , and have the same problem PE
jandujar
New poster

Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

try this.

scanf("%d",&test);

while(test--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf(...);//inputs
}

printf("%.2lf\n",salida);
if(test)printf("\n");
}
cuii e

alu_mathics
Learning poster

Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong

### 10034 P.E.?

I am getting presentation error WHY?????
Done by prims algo.

Code:
#include<stdio.h>
#include<math.h>
main()
{
int t[100][2],nr[101],n,m,i,j,k;
unsigned long c;
float cost[101][101];
float x[101],y[101],x1,y1;
float min,temp;
scanf("%lu",&c);
while(c)
{ min=0.0;c--;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%f %f",&x1,&y1);
x[i]=x1*10;y[i]=y1*10;
}
for(i=1;i<=n;i++) cost[i][i]=0.0;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
cost[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
cost[j][i]=cost[i][j];
}
for(i=2;i<=n;i++) nr[i]=1;
nr[1]=0;

for(i=1;i<n;i++)
{ m=-2;
for(j=2;j<=n;j++)
{
if(nr[j]!=0 && m==-2) m=j;
if(nr[j]!=0)
if(cost[j][nr[j]]<cost[m][nr[m]]) m=j;
}
temp=cost[m][nr[m]]*100;
temp=sqrt(temp);
min=min+temp ;
nr[m]=0;
for(k=2;k<=n;k++)
{
if(nr[k]!=0)
if(cost[k][nr[k]]>cost[k][m]) nr[k]=m;
}
}
printf("%.2f",min/100);
if(c!=0) printf("\n\n");
}
}
sobhani
New poster

Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm

I am not sure, but I got RTE for the following input

1

4
0.0 0.0
1.0 0.0
5.0 0.0
7.0 0.0
Where's the "Any" key?
Solaris
Learning poster

Posts: 99
Joined: Sun Apr 06, 2003 5:53 am

### 10034 Freckles - Java Help!! WA

Hi,

I keep getting WA for this problem.
I used Prims Alg to find the MST.

Is there a special Input case Im Missing?

Any suggestions?

// Code content Removed //.
troy
New poster

Posts: 8
Joined: Fri Jul 23, 2004 10:39 am
Location: New Zealand

PreviousNext