10301 - Rings and Glue

[Joe Smith]

The problem says to output the answer in a gramatically correct sentence.

When X=0, the expected answer is "The largest component contains 0 ring.". This is gramatically incorrect, and should be "0 rings".

[Adrian Kuegel]

You are right. There was a clarification during contest that one has to print 0 ring, but I don't understand why it still is not fixed.

[Rivaldo]

Problem:Rings and Glue
I think it's a very easy problem.I built a graph first, then use DFS to calc the largest component.

[pascal]
const
name1 = '';
name2 = '';
maxn = 100;
var
map : array[1 .. maxn, 1 .. maxn] of boolean;
a,b,c : array[1 .. maxn] of real;
used : array[1 .. maxn] of boolean;
n,res : longint;

procedure init;
var i : integer;
begin
readln(n);
for i := 1 to n do readln(a, b, c);
end;

function covered( p, q : integer) : byte;
var tmp : real;
begin
tmp := sqr(a[p] - a[q]) + sqr(b[p] - b[q]);
if tmp > sqr(c[p] + c[q]) then covered := 0
else if tmp < sqr(c[p] - c[q]) then covered := 2
else covered := 1;
end;

function search( p : integer) : integer;
var i,j : integer;
begin
used[p] := true; j := 1;
for i := 1 to n do
if map[p, i] and not used then
j := j + search(i);
search := j;
end;

procedure main;
var i,j,k : integer;
begin
fillchar(used, sizeof(used), false);
fillchar(map, sizeof(map), false);
for i := 1 to n - 1 do
for j := i + 1 to n do begin
k := covered(i,j);
if k = 1 then begin map[i, j] := true; map[j, i] := true; end;
end;

res := 0;
for i := 1 to n do
if not used then begin
j := search(i);
if j > res then res := j;
end;
end;

procedure print;
begin
if res > 1 then writeln('The largest component contains ', res, ' rings.')
else writeln('The largest component contains ', res, ' ring.');
end;

begin
assign(input, name1);
reset(input);
assign(output, name2);
rewrite(output);
repeat
init;
if n >= 0 then begin
main;
print;
end;
until n = -1;
close(input);
close(output);
end.
[/pascal]

[..]

Hi,

I don't know if your implementation is ok, but I can tell you one thing,
if the largest component is empty, you should print "0 rings", instaed of "0 ring"

Good luck!

[bolster]

Problem statement says "Input consists of a number (>0) of problems. " (i.e. number of test cases). Sample input does not

bolster

[Adrian Kuegel]

Read the whole problem description. It also says "Input ends with a single row with the integer -1".

[htl]

Why does this code get WA? Is anything I didn't consider yet?
[c]
#include<stdio.h>
#include<math.h>
#define SQUARE(x) ((x)*(x))
int place[99],num[99],n;
void put(int,int);
void main(void)
{
int x,y,max;
double data[99][3],r1,r2,d;
while(1)
{
scanf("%d",&n);
if(n<0)
break;
if(n==0)
{
printf("The largest component contains 0 ring.\n");
continue;
}
for(x=0;x<99;x++)
place[x]=-1;
for(x=0;x<n;x++)
place[x]=x,num[x]=1;
for(x=0;x<n;x++)
scanf("%lf %lf %lf",&data[x][0],&data[x][1],&data[x][2]);
for(x=0;x<n;x++)
for(y=x+1;y<n;y++)
{
r1=data[x][2],r2=data[y][2],d=sqrt(SQUARE(data[x][0]-data[y][0])+SQUARE(data[x][1]-data[y][1]));
if(r1+r2>d && r1+d>r2 && r2+d>r1)
if(place[x]!=place[y])
put(x,y);
}
for(x=0,max=0;x<n;x++)
if(num[x]>max)
max=num[x];
if(max>1)
printf("The largest component contains %d rings.\n",max);
else
printf("The largest component contains 1 ring.\n");
}
}
void put(int i,int j)
{
int a,b,x,temp,temp2;
a=num;
b=num[j];
temp=place;
temp2=place[j];
for(x=0;x<n;x++)
if(place[x]==temp || place[x]==temp2)
{
place[x]=temp;
num[x]=a+b;
}
}
[/c]

[Hauser]

I haven't analyzed code too hard, but it is possible that
you haven't consider two equal circles, one over second.

Hauser

[Shih-Chia Cheng]

Output "0 rings" instead of "0 ring". This is a matter of English grammar.

[Mojca Miklavec]

Why is the answer to the 2nd testcase:

3
3.0 2.0 2.0
0.0 -0.5 1.0
0.0 0.0 2.0

"The largest component contains 2 rings."?

Isn't the 3rd ring (0.0,0.0,2.0) glued to both the first and the second one? According to my opinion the answer should be "3".

And what's with "0 ring/rings" again?

Thanks, Mojca

[Picard]

nope, (0.0 0.0 2.0) touches only (3.0. 2.0 2.0). (the rings have a hole inside, so only the perimeter counts)
i used '0 rings'

[scythe]

I got AC with '0 rings'
I guess they changed the data..
[c]void print()
{
int i, max = 0;
for (i = 0; i < N; i++)
if (T == i && Nr > max)
max = Nr;
printf("The largest component contains %d ring", max);
if (max != 1) printf("s");
printf(".\n");
}
[/c]

[Whinii F.]

I get a WA with this code. What's wrong with my code? I'm wondering why..

I build a graph and use dfs to find the number of the vertices included in the maximum component. I did everything that seems suitable..

(though I really hesitated to post a code.. anyway,)

[c]
#include <stdio.h>

int n;
int graph[100][100];

int visited[100];

double y[100], x[100], radius[100];

int readInput(void)
{
int i;
scanf("%d", &n);
if(n == -1)
return 0;
for(i = 0; i < n; i++)
{
scanf("%lf %lf %lf", &x, &y, &radius);
}
return 1;
}

double sqr(double a)
{
return a*a;
}

double max(double a, double b)
{
if(a > b)
return a;
return b;
}

double min(double a, double b)
{
return -max(-a, -b);
}

double equal(double a, double b)
{
if(a > b)
return a - b < 0.000001;
return b - a < 0.000001;
}

int intersect(double y1, double x1, double r1, double y2, double x2, double r2)
{
double dist = sqr(y1-y2)+sqr(x1-x2);
if(equal(x1, x2) && equal(y1, y2) && equal(r1, r2))
return 1;
if(dist < max(r1, r2))
{
return dist + min(r1, r2) > max(r1, r2);
}
else
return dist < sqr(r1+r2);
}

int visit(int cur)
{
int ret = 1, i;
visited[cur] = 1;
for(i = 0; i < n; i++)
if(graph[cur] && !visited)
ret += visit(i);
return ret;
}

void solve(void)
{
int i, j;
int max = 0, res;
/* build a graph */
for(i = 0; i < n-1; i++)
{
graph = 0;
for(j = i+1; j < n; j++)
{
graph[j] = graph[j] = intersect(x, y[i], radius[i], x[j], y[j], radius[j]);
}
}

for(i = 0; i < n; i++)
visited[i] = 0;
for(i = 0; i < n; i++)
if(!visited[i])
{
res = visit(i);
if(res > max)
max = res;
}
if(max <= 1)
printf("The largest component contains %d ring.\n", max);
else
printf("The largest component contains %d rings.\n", max);
}

int main(void)
{
while(readInput())
solve();
return 0;
}
[/c]

[Adrian Kuegel]

You should have really read what has been written so far;
what about
if(max <= 1)
printf("The largest component contains %d ring.\n", max);
it will print 0 ring, but you should print 0 rings.

[Whinii F.]

I forgot to mention that I tried everything that was posted..
code with

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

instead of

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

also results in WA.
What shall I do?

(Oops.. I thought "0 ring" was gramatically correct.. --; )