10301  Rings and Glue
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Whinii F,
your program is wrong for the input:
2
0.1 0.1 1.1
0.0 0.0 1.0
the output will be :
The largest component contains 2 rings.
dist is square of distance. But min(r1,r2) and max(r1,r2) does not return square number.
your program is wrong for the input:
2
0.1 0.1 1.1
0.0 0.0 1.0
the output will be :
The largest component contains 2 rings.
Most probably THese line has some bugs.if(dist < max(r1, r2))
{
return dist + min(r1, r2) > max(r1, r2);
}
dist is square of distance. But min(r1,r2) and max(r1,r2) does not return square number.
__nOi.m....
10301wa pls help.........
I have got WA in the following code.
I don't know where yhe fault is.Can anyone help me??some Sample i/o
will also help......
Code: Select all
#include<stdio.h>
#include<math.h>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 101
int color[MAX];
int adj[MAX][MAX];
int component,maxcomponent;
struct {
double x;
double y;
double r;
}circle[MAX];
void dfs_visit(int i,int vertex)
{
color[i]=GRAY;
for(int j=0;j<vertex;j++)
{
if(adj[i][j]==1)
{
if(color[j]==WHITE)
{
component++;
dfs_visit(j,vertex);
}
}
}
color[i]=BLACK;
}
void dfs(int vertex)
{
int i;
for(i=0;i<MAX;i++)
color[i]=WHITE;
maxcomponent=0;
for(i=0;i<vertex;i++)
{
component=1;
if(color[i]==WHITE)
dfs_visit(i,vertex);
if(component>maxcomponent)
maxcomponent=component;
}
}
double max(double a,double b)
{
if(ab>0.00001)
return a;
return b;
}
double min(double a,double b)
{
if(ab>0.00001)
return b;
return a;
}
int intersect(int i,int j)
{
if(circle[i].x==circle[j].x && circle[i].y==circle[j].y && circle[i].r==circle[j].r)
return 1;
double dis=(circle[i].xcircle[j].x)*(circle[i].xcircle[j].x)+(circle[i].ycircle[j].y)*(circle[i].ycircle[j].y);
dis=sqrt(dis);
if(dis+min(circle[i].r,circle[j].r)max(circle[i].r,circle[j].r<0.00000000000001))
return 0;
double R=circle[i].r+circle[j].r;
if(Rdis>0.00000000000001)
return 1;
return 0;
}
void build_graph(int n)
{
int i,j;
for(i=0;i<n1;i++)
{
adj[i][i]=0;
for(j=i+1;j<n;j++)
adj[i][j]=adj[j][i]=intersect(i,j);
}
}
int calculate(int n)
{
build_graph(n);
dfs(n);
if(maxcomponent==1)
printf("The largest component contains 1 ring.\n");
else
printf("The largest component contains %d rings.\n",maxcomponent);
}
int main()
{
int n,i;
double t;
while(scanf("%i",&n)==1)
{
if(n==1)
break;
if(n==0)
{
printf("The largest component contains 0 rings.\n");
continue;
}
for(i=0;i<n;i++)
{
scanf("%lf",&t);
circle[i].x=t;
scanf("%lf",&t);
circle[i].y=t;
scanf("%lf",&t);
circle[i].r=fabs(t);
}
calculate(n);
}
return 0;
}
will also help......
Becareful about overlaping
I think some peopel get WA because of circle intersection/overlaping. Two circle will overlap if :
** Distance between two center is less or equal (<=) sum of two radius and grater or equal (>=) abs_diff(radius1radius2)
In case of float/double data type using = is not good idea. Rather use fabs(x)<(very small value). Most people know that very well.
Another fact is that in case of 1 print ring and other case print rings
I hope that this is enough to get AC.
** Distance between two center is less or equal (<=) sum of two radius and grater or equal (>=) abs_diff(radius1radius2)
In case of float/double data type using = is not good idea. Rather use fabs(x)<(very small value). Most people know that very well.
Another fact is that in case of 1 print ring and other case print rings
I hope that this is enough to get AC.
10301(Rings and Glue)Wrong Answer????
Can anyone Help me why am I getting WR again and again?
Sorry for giving Code!
#include<stdio.h>
#include<math.h>
#define dtype double
#define range 105
dtype diff(dtype a,dtype b)
{
if(a>b)return ab;
return ba;
}
int setcircle(dtype x[range][3],int info[range],int n)
{
int i,j,maximum;
dtype t1,t2,t3;
if(n<2)return n;
for(i=0;i<n1;i++) for(j=i+1;j<n;j++)
{
t1=(x[i][0]x[j][0])*(x[i][0]x[j][0]);
t2=(x[i][1]x[j][1])*(x[i][1]x[j][1]);
t1=sqrt(t1+t2); t2=x[i][2]+x[j][2]; t3=diff(x[i][2],x[j][2]);
if((t1<t2)&&(t1>t3)) { info[i]++; info[j]++; }
}
maximum=info[0];
for(i=1;i<n;i++) if(info[i]>maximum) maximum=info[i];
return maximum;
}
void main()
{
int i,n,info[range];
dtype x[range][3];
//clrscr();
//freopen("E:\\input.txt","r",stdin);
//freopen("E:\\myput.txt","w",stdout);
while(scanf("%d",&n)==1)
{
if(n==1)break; for(i=0;i<n;i++) info[i]=1;
for(i=0;i<n;i++) scanf("%lf%lf%lf",&x[i][0],&x[i][1],&x[i][2]);
n=setcircle(x,info,n);
if(n==1)printf("The largest component contains 1 ring.\n");
else printf("The largest component contains %d rings.\n",n);
}
}
Sorry for giving Code!
#include<stdio.h>
#include<math.h>
#define dtype double
#define range 105
dtype diff(dtype a,dtype b)
{
if(a>b)return ab;
return ba;
}
int setcircle(dtype x[range][3],int info[range],int n)
{
int i,j,maximum;
dtype t1,t2,t3;
if(n<2)return n;
for(i=0;i<n1;i++) for(j=i+1;j<n;j++)
{
t1=(x[i][0]x[j][0])*(x[i][0]x[j][0]);
t2=(x[i][1]x[j][1])*(x[i][1]x[j][1]);
t1=sqrt(t1+t2); t2=x[i][2]+x[j][2]; t3=diff(x[i][2],x[j][2]);
if((t1<t2)&&(t1>t3)) { info[i]++; info[j]++; }
}
maximum=info[0];
for(i=1;i<n;i++) if(info[i]>maximum) maximum=info[i];
return maximum;
}
void main()
{
int i,n,info[range];
dtype x[range][3];
//clrscr();
//freopen("E:\\input.txt","r",stdin);
//freopen("E:\\myput.txt","w",stdout);
while(scanf("%d",&n)==1)
{
if(n==1)break; for(i=0;i<n;i++) info[i]=1;
for(i=0;i<n;i++) scanf("%lf%lf%lf",&x[i][0],&x[i][1],&x[i][2]);
n=setcircle(x,info,n);
if(n==1)printf("The largest component contains 1 ring.\n");
else printf("The largest component contains %d rings.\n",n);
}
}
Mr. Arithmetic logic Unit
10301 WA
Hi all,
I'm getting WA several times. Please tell me whether my process is correct or wrong.
1. Iterating all posible combination i mean if n=3, then i check
(1,2),(1,3),(2,3) are intersect or not.
2. If intersect ignore it.
3. If not intersect then count each number. I means , for first input, the pairs which is not intersect are (1,4),(2,4),(3,4). Then i check which numbers occurs maximum. Here 4 occurs maximum times(3). Then i output max+1 which is 4.
4. In checking intersection, at first i find the distance between two circles center, if the distance is less than (r1+r2) then intersect, another things if distance is less than the difference between (r1,r2) then not intersect.
Am i right ?
I'm getting WA several times. Please tell me whether my process is correct or wrong.
1. Iterating all posible combination i mean if n=3, then i check
(1,2),(1,3),(2,3) are intersect or not.
2. If intersect ignore it.
3. If not intersect then count each number. I means , for first input, the pairs which is not intersect are (1,4),(2,4),(3,4). Then i check which numbers occurs maximum. Here 4 occurs maximum times(3). Then i output max+1 which is 4.
4. In checking intersection, at first i find the distance between two circles center, if the distance is less than (r1+r2) then intersect, another things if distance is less than the difference between (r1,r2) then not intersect.
Am i right ?

 Experienced poster
 Posts: 183
 Joined: Thu Nov 11, 2004 12:35 pm
 Location: AIUB, Bangladesh
well 1st of all u try this:
when the max=1, i mean only one ring in the max group then print
print
when the max=1, i mean only one ring in the max group then print
elseThe largest component contains 1 ring.
print
if doesn't work then  i have used set union if a circle intersect with another, i put it in the same set. later find it out which one is the biggest set.The largest component contains "max" rings.
Jalal : AIUB SPARKS

 Experienced poster
 Posts: 106
 Joined: Thu Jan 29, 2004 12:07 pm
 Location: Bangladesh
 Contact:

 Experienced poster
 Posts: 106
 Joined: Thu Jan 29, 2004 12:07 pm
 Location: Bangladesh
 Contact:
try this input
output should be
your code gives 3 rings.
ur algorithm is wrong.If ring pair(1, 3) and ring pair(2, 3) is connected 1,3 are also connected. Try dfs, or set union.
bye
Code: Select all
4
0.0 0.0 1.0
0.0 2.1 1.0
0.0 .5 1.0
2.0 2.0 3.5
Code: Select all
The largest component contains 4 rings.
ur algorithm is wrong.If ring pair(1, 3) and ring pair(2, 3) is connected 1,3 are also connected. Try dfs, or set union.
bye
sobhani