10301 - Rings and Glue

[adnan2nd]

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.

[FAQ]

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

Code: Select all

Aced

[mf]

Read the 'Output' section carefully.
"The largest component contains 1 rings." isn't a grammatically correct answer.

[FAQ]

I got AC, the mistake you mentioned + another mistake in compiler
Thanks a lot

[shihabrc]

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
{
	double x,y,rad;
} Circle;

typedef struct Adj_list_
{
	vector<int> v;
} Adj_list;

Circle ring[SIZE];
bool visited[SIZE];
int colour[SIZE];
Adj_list_ adj[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; 
			adj[i].v.clear();
			visited[i]=false;
			scanf("%lf%lf%lf",&ring[i].x,&ring[i].y,&ring[i].rad);
		}
		
		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));
			if(dist<ring[i].rad+ring[j].rad || fabs(dist-fabs(ring[i].rad+ring[j].rad))<EPS )
			{
				if(dist>fabs(ring[i].rad-ring[j].rad) || fabs(dist-fabs(ring[i].rad-ring[j].rad))<EPS )
				{
					adj[i].v.push_back(j);
					adj[j].v.push_back(i);
				}
			}
		}
	}
}

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;
	
	size=adj[u].v.size();

	for(i=0;i<size;i++)
	{
		if(!visited[adj[u].v[i]])
			visit(adj[u].v[i]);
	}
}

-Shihab

[IRA]

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.

[Jan]

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.

[shakil]

Why WA???? Please help......

Code: Select all

[Jan]

Before posting your code, make sure that it passes the samples correctly.

[shakil]

Why WA???? Please help......

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

[asmaamagdi]

Can someone tells me the output for:
2
0 0 1
0 0 1

Should it be 1 ring or 2 rings??!!

[Jan]

My code prints 1 ring for your case.

[asmaamagdi]

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

[Jan]

I just converted all numbers to integers, and used integer calculations.

[ghooo]

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

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