10432 - Polygon Inside A Circle

[jjtse]

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.

[jjtse]

you know the weird thing is?? I converted the code to C++ and it was instantly accepted.

[Darko]

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]

"#####.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]

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]

you are absolutely right.

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

IT should be 0.100!

[ranacse05]

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

[Darko]

Does you calculator give you 22/7=pi?
Define it as acos(-1) or something like that.

[wjomlex]

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]

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

[vahid sanei]

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

[mahi_seu.bd]

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

[nazmul.acmicpc]

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]

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]

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