10301 - Rings and Glue

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » 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.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » 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.
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:

Post by Lamas » 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.
good algorithm is important~

Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:

Post by Lamas » 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. 8)
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.........

Post by Faizur » Mon Jun 30, 2003 8:11 pm

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
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

Becareful about overlaping

Post by Rajib » 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. :lol:

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

10301(Rings and Glue)Wrong Answer????

Post by TISARKER » 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);
}
}
Mr. Arithmetic logic Unit

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

10301 WA

Post by Chok » 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 ?

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » 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-
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

Post by Chok » 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.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » 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.
Jalal : AIUB SPARKS

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

Post by Chok » Sun Jul 10, 2005 9:25 am

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

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

Post by Raiyan Kamal » Mon Sep 05, 2005 2:20 pm

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
Location: Bangladesh
Contact:

Post by Raiyan Kamal » 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.

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

Post by adnan2nd » Fri Oct 07, 2005 12:21 pm

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
sobhani

Post Reply

Return to “Volume 103 (10300-10399)”