356 - Square Pegs And Round Holes

[joydip]

I think I have problem creating formula
My formula is:
Cells contain segments of the circle is =8*n-4
And
Cells completely contained in the circle is=m=2*n*(n-1)
please help

[Joseph Kurniawan]

The first formula is okay. But the second?? it's very far from correct. The failure will occur when n>=5. For n=5, the cells completely contained in the circles are 76, not 40.
I solved this prob using looping method since my geometry isn't so good.

[UFP2161]

If n = 5, then
a) 8*n-4 = 36 [squares w/ segments]
b) 4*n*n = 100 [number of squares]

How can 36+76 > 100 cells? I counted 52 w/ a graphing calculator.

[UFP2161]

There should be a newline between blocks. You have an extra newline at the end of your output.

[Joseph Kurniawan]

Yes, yes my mistake.
76 is the answer for n = 6. For n = 5, you're right, the number of cells is 52. Thnx UFP2161!!

[Joseph Kurniawan]

Well, as far as I know, extra blank lines commonly will only cause P.E.
I suggest not to mix the non floating-point data type (int & long) with floating-point data type (float, double and long double). The method seems alright to me. Just change the int and long type with float or double. As for the extra blank lines, you may use:

[cpp]
if (line) printf("\n");
line=1;
touches_circle = 8*n-4;
[/cpp]

Good luck!!

[joydip]

Thanks I got it and make it A.c

[_.B._]

Greetings!.
I solved problem 356 (http://online-judge.uva.es/cgi-bin/Onli ... Info:42085), but I read there's some formula for it.
Will any of you please e-mail me that formula and why it works?.
Thanks in advance.
bernardolg@cantv.net

[JiaYun]

My program has the same output with an AC code from n = 1 to n = 150, but I can't understand why it got WA.

[cpp]#include <iostream>

using namespace std;

int
main(void)
{
int n;
bool first = true;
while (cin >> n) {
if (!first)
cout << endl;
first = false;

double radiusp2 = n;
radiusp2 -= 0.5;
radiusp2 *= radiusp2;

int segment = 0;
int complete = 0;

for (double i = 0; i < n; i++) {
for (double j = 0; j < n; j++) {
if ( (i+1)*(i+1) + (j+1)*(j+1) < radiusp2 ) {
complete++;
} else if ( i*i + j*j < radiusp2 ) {
segment++;
}
}
}

cout << "In the case n = " << n << ", " << segment * 4
<< " cells contain segments of the circle." << endl
<< "There are " << complete * 4 << " cells completely contained in the circle." << endl;
}

return 0;
}[/cpp]

[UFP2161]

Are you mailing your code in? If so, the really long cout code might be getting broken off at a bad place which would cause a WA.

If so, try submitting it using the online form. Otherwise, I don't know what could be wrong. Matches my AC code as well.

[Mohammad Mahmudur Rahman]

You can solve this problem in an easier way too. Do some pen & paper works for the first few values of n i.e. n = 1,2,3,4... & you will find 2 formula refer to Concrete Math (Knuth) , floor & ceiling functions chapter.

[JiaYun]

to UFP2161:
I modified the cout code and got AC now, thank you!

to Mohammad Mahmudur Rahman:
Thanks for your suggestion, I will try to find the formulas.

[dovier_antonio]

My solution for the problem 356 is :

#include <stdio.h>

int main() {

int n;

while (scanf("%d", &n) != EOF) {

printf("In the case n = %d, %d cells contain segments of the circle.\n", n, 8 * n - 4);
printf("There are %d cells completely contained in the circle.\n\n", 2 * n * (n - 1));

}

return 0;

}

[Mohammad Mahmudur Rahman]

You need to use long int for calculation. Otherwise your program will fail to inputs greater than some 104 or 105, I guess.
& also, why not mentioning the problem number & name in the topic? Surely it increases the chance of getting a reply.

[neno_uci]

Are these formulas ok...???

cells with segments of the circle = 4 * (2 * n - 1) = 8 * n - 4
cells completely contained in the circle = 2 * n * (n - 1)

...???

Thanx in advance,

Yandry.