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
Location: Nevada, US
Contact:

10432 -WA - precision error?

Post by jjtse » Sun Jul 30, 2006 3:15 am

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
Location: Nevada, US
Contact:

Post by jjtse » Sun Jul 30, 2006 3:43 am

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
Location: Calgary, Canada

Post by Darko » Sun Jul 30, 2006 10:47 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?

And, instead of

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
Location: Nevada, US
Contact:

Post by jjtse » Sun Jul 30, 2006 11:23 pm

"#####.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
Location: Calgary, Canada

Post by Darko » Mon Jul 31, 2006 4:21 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
Location: Nevada, US
Contact:

Post by jjtse » Mon Jul 31, 2006 5:41 am

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:

Post by ranacse05 » Sat Apr 21, 2007 8:39 pm

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
Location: Calgary, Canada

Post by Darko » Sat Apr 21, 2007 8:43 pm

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

Post by wjomlex » Thu Jan 15, 2009 9:40 pm

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

Post by newkid » Thu Jan 15, 2009 11:14 pm

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

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

Re: 10432 - ***Strange***

Post by vahid sanei » Wed Feb 25, 2009 8:42 am

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
Location: Bangladesh
Contact:

Re: 10432 - Polygon Inside A Circle

Post by mahi_seu.bd » Tue Dec 14, 2010 7:58 pm

Area=r*r*n*sin((2.0*pi)/n)/2;
shuld be ac..... :P

nazmul.acmicpc
New poster
Posts: 1
Joined: Sat Apr 09, 2011 5:11 am

problem with 10432

Post by nazmul.acmicpc » Sat Apr 09, 2011 5:33 am

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

Post by masum93 » Thu Oct 13, 2011 11:15 am

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

Post by evniiuc » Fri Oct 21, 2011 12:58 am

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;
}

Post Reply

Return to “Volume 104 (10400-10499)”