10283 - The Kissing Circles

[Caesum]

This problem states:
[quote]
So you won

[cyfra]

Hi!

These are my answers for your test cases ...
I think that your error is for the case

10 1

I should be :

10.0000000 0.00000000 0.000000000

Because in other test cases you have quite a similar answer..

So try to change it and test again...

I hope it will help

Good Luck

[Caesum]

thanks, sometimes i cant see for looking

[Dmytro Chernysh]

I got stuck with 10283. And I really don't know where the mistake is.

So, can somebody check my input/output

input
10 1
10 2
10 3
10 4
10 5
10 6
10000 100

output
10.0000000000 0.0000000000 0.0000000000
5.0000000000 157.0796326795 0.0000000000
4.6410161514 3.4732652470 107.6854162259
4.1421356237 14.7279416563 83.8264899217
3.7019190816 29.7315551092 69.1625632742
3.3333333333 45.6568837582 59.0628713615
0.3045417047 304518.1528769724 313854718.0691971200

Thanks for help.

P.S. Still, suck "packing" problems are somewhat... at least strange.

[Red Scorpion]

Hi, Dima

My AC code, give:

Code: Select all

10.0000000000 0.0000000000 0.0000000000
5.0000000000 0.0000000000 157.0796326795
4.6410161514 3.4732652470 107.6854162259
4.1421356237 14.7279416563 83.8264899217
3.7019190816 29.7315551092 69.1625632742
3.3333333333 45.6568837582 59.0628713615
304.5417046668 280844359.6055448100 4178000.5214742422

hope this helps.

[nahidshahin]

I don't know where the error of my code. Why it produce wrong when big number is given.Please some one help me.
Here my code

Code: Select all

#include <stdio.h>
#include <math.h>

void main() {
	long double n,R,r,t,bluearea,greenarea,pi,pi_n,t1;
	pi = 2.0 * acos(0);
	while(scanf("%Lf%Lf",&R,&n) != EOF) {
		if(n==1) {
			printf("%.10Lf %.10Lf %.10Lf\n",R,t1,t1);
			continue;
		}
		else if(n==2) {
			t1 = (pi*R*R);
			greenarea = t1/2.0;
			t = 0;
			printf("%.10Lf %.10Lf %.10Lf\n",R/2.0,t,greenarea);
			continue;
		}
		pi_n = pi / n;
		r = 1.0 + ( 1.0 / sin(pi_n) );
		r = R / r;
		t = 2.0 * r;
		t = t*t;
		t *= (1.0/tan(pi_n)) *n;
		t /= 4.0;
		t1 = pi*r*r;
		bluearea = t - t1*(n-2.0)*0.5;
		greenarea = (pi*R*R) - bluearea - (n*t1);
		printf("%.10Lf %.10Lf %.10Lf\n",r,bluearea,greenarea);
	}
}

if input is

10000 100

ans will be

304.5417046668 280844359.6055448100 4178000.5214742422

But I get

304.5417046668 280844359.6055448230 4178000.5214741787


Thanks

[anupam]

would you please describe the algorithm plz?
I think I have a problem in my algo.
help please.

[GreenPenInc]

My WA code gives nearly the same as you, Red Scorpion. I just don't know what the problem is! The only difference is as follows:

Code: Select all

gpi@grassi 10283 $ diff test foutput 
7c7
< 304.5417046668 280844359.6055448021 4178000.5214741933
---
> 304.5417046668 280844359.6055448100 4178000.5214742422

This looks like the kind of difference that the judge should forgive. What's the matter? Here is my code.

[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

/*********************************************************/
/* Globals */

long double r, I, E;
int R, N;
const long double PI = 3.141592653589793238462643383279;

/*********************************************************/
/* Functions */

/* Calculates the radius of each smaller circle */
void radius(void)
{
if (N < 3)
{
r = R / N;
return;
}
long double num = sin(2.0 / N * PI);
long double denom = 2 * sin((N - 2) / (2.0 * N) * PI) + sin((2.0 / N) * PI);
r = R * num / denom;
}

/* Calculates the blue area */
void internal(void)
{
if (N < 3)
{
I = 0;
return;
}
I = N * r * sqrt(R * R - 2 * r * R) - 0.5 * PI * r * r * (N - 2.0);
}

/* Calculates the leftover area */
void external(void)
{
/* Area of whole circle minus area of all small circles minus I */
E = PI * R * R - N * PI * r * r - I;
}

int main(int argc, char **argv)
{
while (cin >> R >> N)
{
radius();
internal();
external();
printf("%.10Lf %.10Lf %.10Lf\n", r, I, E);
}
return 0;
}
[/cpp]

[Mohammad Mahmudur Rahman]

To GreenPenInc:
I think your algorithm is alright & similar to my AC program but the WA is occuring due to precision errors. Instead of pre-defining PI, use -

Code: Select all

pi = 2 * acos(0.0);

& also change this line -

Code: Select all

if(N<3)
{
      r = R / N;
}

to

Code: Select all

if(N<3)
{
      r = (double)R / N;
}

Hope it helps.

[lonelyone]

I = N * r * sqrt(R * R - 2 * r * R) - 0.5 * PI * r * r * (N - 2.0);

I have no idea to solve blue area, could someone explain it for me.
Especially N * r * sqrt(R * R - 2 * r * R) .
Thanks in advance. ^^

[lonelyone]

I = N * r * sqrt(R * R - 2 * r * R) - 0.5 * PI * r * r * (N - 2.0);

I have no idea to solve blue area, could someone explain it for me.
Especially N * r * sqrt(R * R - 2 * r * R) .
Thanks in advance. ^^

Is there anybody explain this formula for me.
I have no idea to solve the blue area.
Could you just give me some hint.
Thanks a lot.

[jjtse]

did you ever find out what that formula means? It's interesting and I want to know as well.

[crip121]

for input 10000 100, ur output can be different than ACed output posted by red scorpion. i solved this problem using 3 different equation and all of them produced different output for above case but all of those code have gotten AC.

[mpi]

For those stuck in this problem:

The input file will contain several lines of inputs. Each line contains non-negative integers R(R<=10000) and N (1<=N<=100) as described before. Input is terminated by end of file.

It's quite obvious that N is positive but what about R? Do you handle R=0? Well, I didn't
And that's how I usually get dozens of WAs after a thorough analysis