10301 - Rings and Glue

[Adrian Kuegel]

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]

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.

[Lamas]

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.

[Lamas]

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.

[Faizur]

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 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;
}	

I don't know where yhe fault is.Can anyone help me??some Sample i/o
will also help......

[Rajib]

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]

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);
}
}

[Chok]

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]

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.

[Chok]

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]

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.

[Chok]

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

[Raiyan Kamal]

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

[Raiyan Kamal]

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.

[adnan2nd]

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.

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