10283 - The Kissing Circles

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

10283 - The Kissing Circles

Post by Caesum » Fri May 31, 2002 5:37 pm

This problem states:
[quote]
So you won

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi!

Post by cyfra » Fri May 31, 2002 6:40 pm

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 :wink:

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Fri May 31, 2002 6:52 pm

thanks, sometimes i cant see for looking :)

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

10283 - is kissing so easy? :-)

Post by Dmytro Chernysh » Sat Nov 01, 2003 2:03 am

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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Jan 12, 2004 2:16 pm

Hi, Dima :lol: :lol:

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

nahidshahin
New poster
Posts: 8
Joined: Mon Nov 10, 2003 10:54 am
Location: Bangladesh
Contact:

10283

Post by nahidshahin » Sun Mar 28, 2004 4:06 am

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
nahid

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Jun 26, 2004 7:03 am

would you please describe the algorithm plz?
I think I have a problem in my algo.
help please.
"Everything should be made simple, but not always simpler"

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Fri Aug 27, 2004 5:15 pm

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]
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Wed Nov 24, 2004 1:01 am

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. :)
You should never take more than you give in the circle of life.

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Tue Aug 09, 2005 6:02 am

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
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Thu Aug 18, 2005 1:07 pm

lonelyone wrote:
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
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Sun Aug 06, 2006 8:20 am

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

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 10283 - The Kissing Circles

Post by crip121 » Sat Mar 06, 2010 8:44 am

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
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Re: 10283 - The Kissing Circles

Post by mpi » Thu Sep 02, 2010 10:48 am

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 :oops:
And that's how I usually get dozens of WAs after a thorough analysis :evil:

Post Reply

Return to “Volume 102 (10200-10299)”