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

New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Contact:
chok's 1st algorithm was wrong.
if there r 4 rings, and (1,3) ,(2,3),(2,4) are coonected pair answer should be 4, not 3.
set union- is OK.
sobhani

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

### I still got WA :'(

I searched forum for some tests and passed all of them, but still WA. Please help me

Code: Select all

``````Aced
``````
Last edited by FAQ on Sun Mar 05, 2006 12:06 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Read the 'Output' section carefully.
"The largest component contains 1 rings." isn't a grammatically correct answer.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
I got AC, the mistake you mentioned + another mistake in compiler
Thanks a lot

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

### 10301 Glued with WA

Hi all,

I've tried 2 solve this prob with DFS. But getting WA. I've considered 2 circles overlap if dist. between centres >=sum of rad && <=difference of rad. And I've printed "0 rings". instead of"0 ring". Can some1 hlp plz. I'm givin the code below.

Code: Select all

``````#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>

using namespace std;

#define EPS 1e-9
#define SIZE 100

typedef struct Circle
{
} Circle;

{
vector<int> v;

Circle ring[SIZE];
bool visited[SIZE];
int colour[SIZE];
int nRings,component;

void build_graph();
void DFS();
void visit(int);

void main()
{
int i,max,temp;

//freopen("C:\\4.txt","rb",stdin);

while(scanf("%d",&nRings)==1)
{
if(nRings<0) break;

for(i=0;i<nRings;i++)
{
colour[i]=0;
visited[i]=false;
}

build_graph();
DFS();
max=-1;

for(i=1;i<=nRings;i++)
{
temp=count(colour,colour+nRings,i);
if(temp>max) max=temp;
}

if(max==1) printf("The largest component contains %d ring.\n",max);
else printf("The largest component contains %d rings.\n",max);

}
}

void build_graph()
{
int i,j;
double dist;
for(i=0;i<nRings;i++)
{
for(j=i+1;j<nRings;j++)
{
dist=sqrt((ring[i].x-ring[j].x)*(ring[i].x-ring[j].x)+(ring[i].y-ring[j].y)*(ring[i].y-ring[j].y));
{
{
}
}
}
}
}

void DFS()
{
int i;
component=1;

for(i=0;i<nRings;i++)
{
if(!visited[i])
{
visit(i);
component++;
}
}
}

void visit(int u)
{
int i,size;
visited[u]=true;colour[u]=component;

for(i=0;i<size;i++)
{
}
}
``````
-Shihab
Shihab
CSE,BUET

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
I used set-union to solve the problem but it always got WA
My code as follow
Who can help me to find the mistake?

Code: Select all

``````I find my mistake and get AC!
``````

The input data
4
0.0 0.0 1.0
-1.5 -1.5 0.5
1.5 1.5 0.5
-2.0 2.0 3.5
3
3.0 2.0 2.0
0.0 -0.5 1.0
0.0 0.0 2.0
5
-2.0 0.0 1.0
1.0 -1.0 1.0
0.0 1.0 0.5
2.0 0.0 1.0
-1.0 1.0 1.0
4
0.0 0.0 1.0
0.0 2.1 1.0
0.0 .5 1.0
-2.0 2.0 3.5
2
0.1 0.1 1.1
0.0 0.0 1.0
-1
My Output:
The largest component contains 4 rings.
The largest component contains 2 rings.
The largest component contains 3 rings.
The largest component contains 3 rings.
The largest component contains 2 rings.
Last edited by IRA on Fri Jan 12, 2007 7:09 pm, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My accepted code returns the following

Output:

Code: Select all

``````The largest component contains 4 rings.
The largest component contains 2 rings.
The largest component contains 3 rings.
The largest component contains 4 rings.
The largest component contains 2 rings.``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:
Last edited by shakil on Sat Jun 30, 2007 6:34 am, edited 1 time in total.
SHAKIL

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Before posting your code, make sure that it passes the samples correctly.
Ami ekhono shopno dekhi...
HomePage

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Code: Select all

``````#include<stdio.h>
#include<math.h>
long double x[109],y[109],t,t1,r[109];

void main()
{
long n,i,j,count,max;

while(1)
{
scanf("%ld",&n);
if(n==-1)
break;

for(i=0;i<n;i++)
scanf("%Lf %Lf %Lf",&x[i],&y[i],&r[i]);

max=0;

for(i=0;i<n;i++)
{
count=0;

for(j=0;j<n;j++)
if(i!=j)
{
t=x[i]-x[j];
t=t*t;
t1=y[i]-y[j];
t1=t1*t1;
t=t+t1;
if(t<=(r[i]+r[j])*(r[i]+r[j]))
{
t1=r[i]-r[j];
if(t1<0)
t1=-t1;
if(t1*t1<=t)
count++;
}
}
count++;
if(count>max)
max=count;
}

printf("The largest component contains %ld ring", max);
if (max != 1) printf("s");
printf(".\n");
}
}
``````
Jan now you can help me.....
My program give all output of the sample input.......
SHAKIL

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt
Can someone tells me the output for:
2
0 0 1
0 0 1

Should it be 1 ring or 2 rings??!!
---
Asmaa Magdi

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My code prints 1 ring for your case.
Ami ekhono shopno dekhi...
HomePage

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt
Thnx Jan for ur reply.
This is what I was doing before and I got WA. I really don't know the trick here :S
---
Asmaa Magdi

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I just converted all numbers to integers, and used integer calculations.
Ami ekhono shopno dekhi...
HomePage

ghooo
New poster
Posts: 3
Joined: Tue Sep 01, 2009 2:13 pm

### Re: 10301 - Rings and Glue

I got AC after considering these cases
the output should be:

....1 ring.
....0 rings.
....x rings.