Posted:

**Sun Oct 27, 2002 3:51 pm**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.

Everything else looks almost equal to my code.

Page **2** of **4**

Posted: **Sun Oct 27, 2002 3:51 pm**

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.

Everything else looks almost equal to my code.

Posted: **Thu Mar 13, 2003 12:51 pm**

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.

Posted: **Sun May 25, 2003 12:58 pm**

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.

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.

Posted: **Sun May 25, 2003 1:14 pm**

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.

So there would not be 0 ring/rings problem over there.

Posted: **Mon Jun 30, 2003 8:11 pm**

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(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++)
{
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......

Posted: **Mon Apr 18, 2005 3:05 pm**

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.

** Distance between two center is less or equal (<=) sum of two radius

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

I hope that this is enough to get AC.

Posted: **Wed May 18, 2005 8:17 pm**

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][3],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][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 a-b;

return b-a;

}

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<n-1;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);

}

}

Posted: **Fri Jul 08, 2005 11:06 am**

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 ?

Posted: **Fri Jul 08, 2005 7:04 pm**

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 1ring.

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.

Posted: **Sat Jul 09, 2005 5:47 am**

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.

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.

Posted: **Sat Jul 09, 2005 5:53 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.

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.

Posted: **Sun Jul 10, 2005 9:25 am**

Hi CodeMaker,

I got accepted yesterday. I used set-union and also <= . Thanx for ur help.

I got accepted yesterday. I used set-union and also <= . Thanx for ur help.

Posted: **Mon Sep 05, 2005 2:20 pm**

Precision error is not a problem here. I got AC simply using >= and <=.

Posted: **Mon Sep 05, 2005 2:27 pm**

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.

Posted: **Fri Oct 07, 2005 12:21 pm**

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