10432 - Polygon Inside A Circle

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

Moderator: Board moderators

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Contact:

10432 -WA - precision error?

My code is simple enough to understand. It is clean and simple. From the other topics regarding this issue, it's most likely a precision problem, but I can't see how I can improve precision from what I already have. Please take a look, thanks.

Code: Select all

\\code removed after accepted.

Last edited by jjtse on Mon Jul 31, 2006 5:40 am, edited 1 time in total.

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Contact:
you know the weird thing is?? I converted the code to C++ and it was instantly accepted.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
I have a different formula and I use my own formatting. I never used DecimalFormat, what does"#####.000" do? Does it round it? What if there are more digits to the left of the decimal point?

Code: Select all

angle = 360.0 / n;
otherAngle = (180 - angle)/2;
height = Math.sin(otherAngle*Math.PI/180) * r;
why not use

Code: Select all

angle = 2 * Math.PI / n;
otherAngle = (Math.PI - angle)/2;
height = Math.sin(otherAngle) * r;

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Contact:
"#####.000" does the following:

Each "#" symbol represents a digit : (0,9].
Each "0" symbol represents a digit: [0,9].
and it does round.

3.14159 ==> 3.142
0.1 ==> .100

I have did a trial experiment and even if there are more than 5 digits before the decimal, it will still print regularly.

What formatting method do you use?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Well, that .100 should probably be 0.100?
I use this (not much, but works for me):

Code: Select all

private String fmt(double d, int prec) {
long pow10 = 1;
for (int i = 0; i < prec; i++) {
pow10 *= 10;
}
long l = Math.round(pow10 * d);
String sign = "";
if (l < 0) {
sign = "-";
l = 0 - l;
}
String s = Long.toString(l);
int len = s.length();
for (int i = 0; i < prec + 1 - len; i++) {
s = "0" + s;
}
len = s.length();
return sign + s.substring(0, len - prec) + "."
+ s.substring(len - prec);
}

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Contact:
you are absolutely right.

I changed my code from "#####.000" to "####0.000" and it worked.

IT should be 0.100!

ranacse05
New poster
Posts: 37
Joined: Wed Mar 28, 2007 5:08 pm
Location: Rajshahi
Contact:
My calculator gives me 12.566 as output for input 2 2000 but my program gives output 12.571 where is the bug?

Code: Select all

#include  "stdio.h"
#include  "math.h"

int main()
{
int R,L;
double r,l,area,con,pi=22.0/7.0,re=pi/180.0;
double x,s;

while(scanf("%d %d",&R,&L)==2)
{
r=(double)R;
l=(double)L;

con=360.0/l;
con*=re;
x=cos(con);
x=sqrtl(r*r+r*r-x*2.0*r*r);
s=(x+r+r)/2.0;
s=sqrtl(s*(s-r)*(s-r)*(s-x));
area=fabs(s)*l;

printf("%.3lf\n",area);
}
return 0;
}
I like to solve problems.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Does you calculator give you 22/7=pi? Define it as acos(-1) or something like that.

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

Re: 10432 - Polygon Inside A Circle

I'm having the same sort of precision issue, but in Java. I'm assuming that Math.PI is the closest value to PI that a double can hold. I've tried acos(-1.0) and 2*acos(0.0) and I've tried three different ways of calculating the answer (as you can see). None of them are good enough for the judge. Does anybody have any ideas on how to make this work in Java?

Code: Select all

import java.util.*;

public class Main
{
public static void main(String args[])
{
Scanner scan = new Scanner(System.in);

while(scan.hasNextDouble())
{
double r = scan.nextDouble();
double n = scan.nextDouble();

double c, C, a, s;

C = 2*Math.PI / n;

c = 2*r*r * (1.0 + Math.cos(C));
c = Math.sqrt(c);

//heron
s = (r + r + c) / 2.0;
a = 0.25 * Math.sqrt( (r+(r+c)) * (c-(r-r)) * (c+(r-r)) * (r+(r-c)) ); //STABLE
//a = Math.sqrt(s * (s-r) * (s-r) * (s-c)); //UNSTABLE
//a = 0.5 * r * r * C; //SIMPLER/INACCURATE
a *= n;

System.out.printf("%.3f\n", a);
}
}
}

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 10432 - Polygon Inside A Circle

My accepted code uses this formula to compute the result in C++,

Code: Select all

//a = 0.5 * r * r * C; //SIMPLER/INACCURATE
the only difference is my variables are long doubles..

In java i think there is no long double.. the doubles are 8 bytes long.
From the old ranklist http://acm.uva.es/p/problemstatnew.php?prob=10432&d=0 i see only few has solved it in java.
as (0<r<20000) & (2<n<20000), you can try multiplying with some large number i.e: 1000000 and divide the result later.. but i am not sure whether it will work..
hmm..

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10432 - ***Strange***

i found size of polygon side
and i calculated area of each triangle with this formula :
*** B is radius and A is side of polygon

Code: Select all

return sqrt(((A*A+B*B+B*B)*(A*A+B*B+B*B))-2*(pow(A,4.0)+pow(B,4.0)+pow(B,4.0)))/4.0;
i thought here exist error for result of area so i use EPS but i got WA
i change my formula to :

Code: Select all

A/=2.0;
double beta ;	beta = acos((A)/B);
double precu;	precu=B*sin(beta);
return A*precu;// area of each triangle
and i got Acc , why ????
Impossible says I`m possible

mahi_seu.bd
New poster
Posts: 4
Joined: Mon Dec 06, 2010 8:25 pm
Contact:

Re: 10432 - Polygon Inside A Circle

Area=r*r*n*sin((2.0*pi)/n)/2;
shuld be ac..... nazmul.acmicpc
New poster
Posts: 1
Joined: Sat Apr 09, 2011 5:11 am

problem with 10432

Uva is not accepting the following code. It's saying the program is running beyond the time limit ! Can anyone help me out plz..

#include<stdio.h>
#include<math.h>
#define pi 3.1416

int main ()
{
int n,r;
float a;
scanf("%d %d", &r, &n);

a = n*r*r* sin( 2*pi*pi/(n*180) )/2;

printf("%.3f", a);

return 0;
}

masum93
New poster
Posts: 7
Joined: Wed May 11, 2011 11:15 am

Re: problem with 10432

nazmul.acmicpc wrote:Uva is not accepting the following code. It's saying the program is running beyond the time limit ! Can anyone help me out plz..

a = n*r*r* sin( 2*pi*pi/(n*180) )/2;
Your angle finding formula is not correct. A regular convex n-gon has a total of (n-2)*180 degrees, and convert it into radian using pi radian=180 degree

evniiuc
New poster
Posts: 1
Joined: Fri Oct 21, 2011 12:38 am

Re: 10432 - Polygon Inside A Circle

My output is ok bt um getting WA dont knw why.plz help me out.
here is my code

#include<stdio.h>
#include<math.h>
int main()
{
double n,r,s;
while(scanf("%lf%lf",&r,&n)==2)
{
printf("%.3lf\n",(r*r*n*sin(2*3.14159265/n))/2);
}
return 0;
}