10991 - Region

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

Moderator: Board moderators

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

10991 - Region

Post by TISARKER » Sun Feb 12, 2006 12:09 pm

I am getting wrong answer.
My output does not match for sample input.
For each test case, my procedure is.
1.Read R1,R2,R3.
Make a triange by center of given 3 circles.
2.
Evaluate 3 sides of the triangle.
s12=R1+R2; s13=R1+R3; s23=R2+R3;
Finf out Area of the triangle.
Suppose Area is A.
3.
Find out angle of each point of the triangle.
A1=asin((2*A)/(s12*s13))
A2=Same formulae.
A3=Same formulae.
Convert A1,A2,A3 into degree from radian.
4.Find out area of part of each circle which is inside triangle.
v1=(pi*R1*R1*A1)/360
v2=same process
v3=same process
5.Sum=v1+v2+v3.
5.result=A-sum.
6.Display result with 6 decimal place.

Code: Select all

Delete Code
Last edited by TISARKER on Sun Feb 12, 2006 3:34 pm, edited 3 times in total.
Mr. Arithmetic logic Unit

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Feb 12, 2006 12:26 pm

On the first glance, the way you compute the angles will fail for triangles where one of the angles is larger than 90 degrees. Note that from the sine of the angle you can't tell whether it is x or (180 degrees-x). Use cosine instead.

Also, your currently posted code doesn't compile under my gcc.

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Post by TISARKER » Sun Feb 12, 2006 1:43 pm

misof wrote:On the first glance, the way you compute the angles will fail for triangles where one of the angles is larger than 90 degrees. Note that from the sine of the angle you can't tell whether it is x or (180 degrees-x). Use cosine instead.
I convert sina into cosa
I above code is modifided
But not getting inprovement :cry:
Please help me.
Last edited by TISARKER on Sun Feb 12, 2006 1:56 pm, edited 1 time in total.
Mr. Arithmetic logic Unit

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Post by TISARKER » Sun Feb 12, 2006 1:55 pm

Sorry for double posting :P
Last edited by TISARKER on Sun Feb 12, 2006 2:04 pm, edited 1 time in total.
Mr. Arithmetic logic Unit

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Sun Feb 12, 2006 2:01 pm

Use The Cosine Law(Theorem).

a^2 = b^2 + c^2 - 2bc cosA
Sorry For My Poor English.. :)

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Feb 12, 2006 2:03 pm

You missed the point. You need the exact value of the cosine, including its sign. For angles between 90 and 180 degrees the cosine is negative, and this is how acos() can tell that the original angle is obtuse. When you compute the cosine from the sine, you won't get the correct sign.

see: http://mathworld.wolfram.com/LawofCosines.html

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Post by TISARKER » Sun Feb 12, 2006 4:31 pm

Thanks misof :D
Thanks wook :D
Mr. Arithmetic logic Unit

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Mon Feb 13, 2006 9:12 pm

i got ac using sine formula as tisarker did first. there may be at most one angle greater than 90 degrees. so i checked if the angle is greater than 90 degrees, and if found i subtracted the angle from 180 degrees.

Code: Select all

      A = asin(2*del/b/c);
      B = asin(2*del/a/c);
      C = asin(2*del/a/b);
      if(b*b+c*c < a*a)  // A > 90 degrees
      	A = pi - A;
      else if(a*a+b*b < c*c)  // C > 90 degrees
      	C = pi - C;
      else if(c*c+a*a < b*b)  // B > 90 degrees
      	B = pi - B;
here del is the area of the triangle, and it is a good idea never to use degrees instead of radians.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Mon Feb 13, 2006 9:14 pm

i got ac using sine formula as tisarker did first. there may be at most one angle greater than 90 degrees. so i checked if the angle is greater than 90 degrees, and if found i subtracted the angle from 180 degrees.

Code: Select all

      A = asin(2*del/b/c);
      B = asin(2*del/a/c);
      C = asin(2*del/a/b);
      if(b*b+c*c < a*a)
      	A = pi - A;
      else if(a*a+b*b < c*c)
      	C = pi - C;
      else if(c*c+a*a < b*b)
      	B = pi - B;
here del is the area of the triangle, and it is a good idea never to use degrees instead of radians.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 13, 2006 10:12 pm

I still think using cosine formula should be preferred, although sine formula with additional checking can be used. During actual contests, it's easy to forget checking the conditions for the sine formula.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Tue Feb 14, 2006 7:21 am

How come no one has ever bothered about the apparent discrepancy in
the problem description?
Prob desctiption:Output

Code: Select all

For each line of input, generate one line of output containing the area of G rounded to six decimal digits after the decimal point. Floating-point errors will be ignored by special judge program.
and the sample i/o
Input

Code: Select all

2
5.70 1.00 7.89
478.61 759.84 28.36
Output

Code: Select all

1.2243
2361.0058
with only 4 places of decimal. My AC prog has more than two zeroes
following each of these two output. This cost me a WA!

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Tue Feb 14, 2006 8:07 am

I have been bothered, too.
My AC Program outputs

Code: Select all

1.224323
2361.005761
In fact, at first, my output format was rounded to four decimal digits after the decimal point,

i.e.

Code: Select all

if(-EPS <= area && area <= EPS)
	printf("0.000000\n", area);
else printf("%.4lf\n", area);
This gave me WA.
I didn't read the problem description CAREFULLY.


but, instead, the output format like

Code: Select all

if(-EPS <= area && area <= EPS)
	printf("0.000000\n", area);
else printf("%.6lf\n", area);
gave me ACCEPTED.
what a strange happening!

well, I can't understand why the example of output is of only 4 places of decimal.
It should be changed, I think.
Sorry For My Poor English.. :)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Feb 14, 2006 8:24 am

Well you might call it a "discrepancy", but I think if the problem statement has made that clear and you miss it, you have got no one to blame.

Still, it would be good if the sample I/O is changed.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Tue Feb 14, 2006 10:04 am

Observer wrote:Well you might call it a "discrepancy",
... as in discordance, disagreement;
Observer wrote: but I think if the problem statement has made that clear and you miss it, you have got no one to blame.
0. I was not blaming some[one|thing], but was musing aloud.
1. The problem statement body & sample i/o make one whole: at least to me, and I don't
see any reason to trust one figure more than a host of others ;)
2. I agree that setting problems is a tough thing, which is why I didn't bother to write about
this issue to the contest clarificator(s) during the contest. However, I was hoping, by now
a correction's due.

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

10991 - Region

Post by Roby » Mon Mar 06, 2006 3:26 am

I just want to know if the cosine of sine theorem valid for this problem... I mean, are these theorem can be used to solve this problem? Here are the theorem page: http://digilib.brawijaya.ac.id/virtual_ ... 203-1e.htm

Thanx in advance :)

Post Reply

Return to “Volume 109 (10900-10999)”