## 10301 - Rings and Glue

Moderator: Board moderators

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
It seems to be the intersection function that is wrong, I pasted it in my accepted program and got WA.
Everything else looks almost equal to my code.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
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.
if(dist < max(r1, r2))
{
return dist + min(r1, r2) > max(r1, r2);
}
Most probably THese line has some bugs.
dist is square of distance. But min(r1,r2) and max(r1,r2) does not return square number.
__nOi.m....

Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:
Hello, every body! First post!!!
Don't be misled by Joe, the answer of that question would never be 0;
There will be at least one ring, the boy can pick up. Unless n is Zero, but if so, the question is meaningless.
good algorithm is important~

Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:
The problem say n is always >0, unless the end, so it would no be 0. The is to say the answer of that problem would never be 0. As the guy at least can pick up 1 ring. So there would not be 0 ring/rings problem over there.
good algorithm is important~

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

### 10301wa pls help.........

I have got WA in the following code.

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 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(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(a-b>0.00001)
return a;
return b;
}
double min(double a,double b)
{
if(a-b>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].x-circle[j].x)*(circle[i].x-circle[j].x)+(circle[i].y-circle[j].y)*(circle[i].y-circle[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(R-dis>0.00000000000001)
return 1;

return 0;
}
void build_graph(int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;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;
}	``````
I don't know where yhe fault is.Can anyone help me??some Sample i/o
will also help......

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am

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(radius1-radius2)

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. TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

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 a-b;
return b-a;
}

int setcircle(dtype x[range],int info[range],int n)
{
int i,j,maximum;
dtype t1,t2,t3;
if(n<2)return n;
for(i=0;i<n-1;i++) for(j=i+1;j<n;j++)
{
t1=(x[i]-x[j])*(x[i]-x[j]);
t2=(x[i]-x[j])*(x[i]-x[j]);
t1=sqrt(t1+t2); t2=x[i]+x[j]; t3=diff(x[i],x[j]);
if((t1<t2)&&(t1>t3)) { info[i]++; info[j]++; }
}
maximum=info;
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];
//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],&x[i],&x[i]);
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

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

### 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 ?

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
well 1st of all u try this:
when the max=1, i mean only one ring in the max group then print-
The largest component contains 1 ring.
else
print-
The largest component contains "max" rings.
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.
Jalal : AIUB SPARKS

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong
Hi Codemaker,
I did it. And the second things that u told is works exactly like me. I want to know weither my intersection generating process is ok or not. Thanx.

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
r u using < (less than)?
if so then it will not work as the problem discription says intersection at one point means no intersection.

i used <= for no intersect and i tried to find out the no intersection case rather than finding when it intersect. it makes things easy.
Jalal : AIUB SPARKS

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong
Hi CodeMaker,
I got accepted yesterday. I used set-union and also <= . Thanx for ur help. Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
Precision error is not a problem here. I got AC simply using >= and <=.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
For two identical circles, you have to count both of them. In general, if there are N identical circles, you have to consider all N of them connected.

New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Contact:
try this input

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``````
output should be

Code: Select all

``````The largest component contains 4 rings.
``````