356  Square Pegs And Round Holes
Moderator: Board moderators

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
I don't know what's wrong with your program.
But I suggest that you can think the problem
in another way.
Try to consider only 1/4 graph.
Then to check each grid,if the distance from left_up point to original point is larger
than (2*n1)/2,the grid is out of circle.
Else if the distance form right_down point
to original point is less than (2*n2)/2,
the grid is in the circle.
Finally,the grid covered by circle is determined by n*n(#of in circle)(# of out circle)
But I suggest that you can think the problem
in another way.
Try to consider only 1/4 graph.
Then to check each grid,if the distance from left_up point to original point is larger
than (2*n1)/2,the grid is out of circle.
Else if the distance form right_down point
to original point is less than (2*n2)/2,
the grid is in the circle.
Finally,the grid covered by circle is determined by n*n(#of in circle)(# of out circle)
I don't know what's wrong with your program.
But I suggest that you can think the problem
in another way.
Try to consider only 1/4 graph.
Then to check each grid,if the distance from left_up point to original point is larger
than (2*n1)/2,the grid is out of circle.
Else if the distance form right_down point
to original point is less than (2*n1)/2,
the grid is in the circle.
Finally,the grid covered by circle is determined by n*n(#of in circle)(# of out circle)
But I suggest that you can think the problem
in another way.
Try to consider only 1/4 graph.
Then to check each grid,if the distance from left_up point to original point is larger
than (2*n1)/2,the grid is out of circle.
Else if the distance form right_down point
to original point is less than (2*n1)/2,
the grid is in the circle.
Finally,the grid covered by circle is determined by n*n(#of in circle)(# of out circle)
I don't know what is my program's wrong...
/* @JUDGE_ID: 14991MR 356 C "Dynamic Programming" */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
float radius ;
int com , seg , n , x , y ;/*, y1;*/
while(scanf("%d" , &n)!=EOF) {
com = 0;
seg = 0;
radius = (float)(2*n1)/2;
if (n==0)
seg = 0;
else
seg = (2*n1)*4;
for (x=0 ; (x+1)<radius ; x++) {
y = (int)sqrt(radius * radius  (x+1) * (x+1));
com = com + y;
/* y1 = (int)sqrt(radius * radius  x * x);*/
/* seg = seg + (y1y+1);*/
}
com = 4 * com;
/*seg = 4 * seg;*/
printf("In the case n = %d, %d cells contain segments of the circle.n" , n , seg);
printf("There are %d cells completely contained in the circle.nn" , com);
}
}
/* @JUDGE_ID: 14991MR 356 C "Dynamic Programming" */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
float radius ;
int com , seg , n , x , y ;/*, y1;*/
while(scanf("%d" , &n)!=EOF) {
com = 0;
seg = 0;
radius = (float)(2*n1)/2;
if (n==0)
seg = 0;
else
seg = (2*n1)*4;
for (x=0 ; (x+1)<radius ; x++) {
y = (int)sqrt(radius * radius  (x+1) * (x+1));
com = com + y;
/* y1 = (int)sqrt(radius * radius  x * x);*/
/* seg = seg + (y1y+1);*/
}
com = 4 * com;
/*seg = 4 * seg;*/
printf("In the case n = %d, %d cells contain segments of the circle.n" , n , seg);
printf("There are %d cells completely contained in the circle.nn" , com);
}
}

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
I'm not exactly sure what you mean, so I will post my method here.
First, my program also only considers 1/4 of a circle, and it happens to be the topright quarter. For every square, I check the bottomleft and topright points. If both are in the circle then the square is in the circle, if only the bottomleft then this square is a segment of the circle, else it is not in the circle. Then I multiply my results by 4 to get final results.
As said before, my program gives exactly the same output as an AC program. Can anyone spot any mistake?
First, my program also only considers 1/4 of a circle, and it happens to be the topright quarter. For every square, I check the bottomleft and topright points. If both are in the circle then the square is in the circle, if only the bottomleft then this square is a segment of the circle, else it is not in the circle. Then I multiply my results by 4 to get final results.
As said before, my program gives exactly the same output as an AC program. Can anyone spot any mistake?

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
TaChung: One mistake in your program is that you claim to use "Dynamic Programming". Although this will not change your result, this wrong comment is soooo annoying in the ranklists, especially when you don't actually used DP.
Please, everybody: If you write a comment, make sure it makes sense. Plus: don't give away the solution.
Please, everybody: If you write a comment, make sure it makes sense. Plus: don't give away the solution.

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
TaChung: Sorry, that example won't help you much. Your program computes that correctly. In fact, your program computes the same as mine for all inputs.
But it's even better: I just got your program accepted without changing it!
Why do people continue posting their correct solutions here when there's nothing wrong? Could you please resubmit it and look at the "Program Received" mail from them? Is that program identical to the one you sent? I'd like to know where this problem comes from.
But it's even better: I just got your program accepted without changing it!
Why do people continue posting their correct solutions here when there's nothing wrong? Could you please resubmit it and look at the "Program Received" mail from them? Is that program identical to the one you sent? I'd like to know where this problem comes from.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
Youre right, that's probably it. Seems like many people have trouble with their mail programs.
Btw, third alternative:
Btw, third alternative:
Code: Select all
printf( "In the case n = %d, %d cells "
"contain segments of the circle.n", n, seg );

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
My program is definitely wrong. This is the code:
Can anyone find any problems?
<font size=1>[ This Message was edited by: junjieliang on 20020316 14:13 ]</font>
Code: Select all
@begin_of_source_code
{@JUDGE_ID: XXXXXX 356 PASCAL}
program square_pegs_and_round_holes(input,output);
const
epsilon : real = 0.0000001;
type
Tinteger = integer;
Tstore = record hal, ful : Tinteger end;
var
num, i, j, half, full : Tinteger;
store : array[0..150] of Tstore;
(*********************************)
function in_circle(x, y : Tinteger) : Boolean;
var
len, dist : real;
begin
dist := sqrt(x * x + y * y);
len := (2 * num  1) / 2;
if (dist  len > epsilon) then in_circle := FALSE else in_circle := TRUE;
end;
(*************************)
begin
for num := 1 to 150 do begin
full := 0;
half := 0;
for i := 0 to num  1 do
for j := 0 to num  1 do begin
if (in_circle(i, j) = TRUE) then begin
if (in_circle(i + 1, j + 1) = TRUE) then full := full + 1
else half := half + 1;
end;
end;
full := full * 4;
half := half * 4;
store[num].ful := full;
store[num].hal := half;
end;
while not eof(input) do begin
readln(num);
if (num <= 0) OR (num > 150) then while TRUE do writeln('CRAP');
writeln('In the case n = ',num,', ',store[num].hal,' cells contain segments of the circle.');
writeln('There are ',store[num].ful,' cells completely contained in the circle.');
if not eof(input) then writeln;
end;
end.
@end_of_source_code
<font size=1>[ This Message was edited by: junjieliang on 20020316 14:13 ]</font>
356,where is the wrong
can u pls point out the wrong .here is my source code,I dont know why it is wrong,help me please
#include<stdio.h>
#include<math.h>
void main()
{
int n,touches_circle,k;
long a=0,b=0;
double radius,temp;
while(scanf("%d",&n)==1)
{
touches_circle = 8*n4;
if(touches_circle<0)touches_circle=0;
radius=n0.5;
radius=radius*radius;
for(k=1;k<n;k++)
{
temp=radiusk*k;
temp=sqrt(temp);
a=(long)temp;
b=b+a;
}
b=4*b;
printf("In the case n = %d, %d cells contain segments of the circle.\n",n,touches_circle);
printf("There are %ld cells completely contained in the circle.\n\n",b);
b=0;
}
}
[cpp][/cpp]
#include<stdio.h>
#include<math.h>
void main()
{
int n,touches_circle,k;
long a=0,b=0;
double radius,temp;
while(scanf("%d",&n)==1)
{
touches_circle = 8*n4;
if(touches_circle<0)touches_circle=0;
radius=n0.5;
radius=radius*radius;
for(k=1;k<n;k++)
{
temp=radiusk*k;
temp=sqrt(temp);
a=(long)temp;
b=b+a;
}
b=4*b;
printf("In the case n = %d, %d cells contain segments of the circle.\n",n,touches_circle);
printf("There are %ld cells completely contained in the circle.\n\n",b);
b=0;
}
}
[cpp][/cpp]

 New poster
 Posts: 8
 Joined: Tue Jul 23, 2002 9:15 am
SAME PROBLEM
Hi,
I have solved the problem in the following way.. It satisfies the example input and output but generate a wrong answer when I submit it.
Can u say what's the wrong here
#include<stdio.h>
void main(){
long n,com_in,out;
while(scanf("%ld",&n)==1){
com_in =2*n*(n1);
out = 4*(2*n1);
printf("In the case n = %ld,",n);
printf(" %ld cells contain ",out);
printf("segments of the circle.\n");
printf("There are %ld cells ",com_in);
printf("completely contained in the circle.\n\n");
}
}
/*@END_OF_SOURCE_CODE*/
I have solved the problem in the following way.. It satisfies the example input and output but generate a wrong answer when I submit it.
Can u say what's the wrong here
#include<stdio.h>
void main(){
long n,com_in,out;
while(scanf("%ld",&n)==1){
com_in =2*n*(n1);
out = 4*(2*n1);
printf("In the case n = %ld,",n);
printf(" %ld cells contain ",out);
printf("segments of the circle.\n");
printf("There are %ld cells ",com_in);
printf("completely contained in the circle.\n\n");
}
}
/*@END_OF_SOURCE_CODE*/
HEY WANT TO GET SOL.TRY ON http://www.uvexam.zzn.com from 1st September