ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1020. Rope

my program is correct, please tell me my error WA #4
Posted by mirzauzairbaig 15 Jan 2010 14:43
#include <iostream>
#include <cmath>
using namespace std;
int main(){
double PI=acos(-1.0);
int N; double r(0), perimeter(0);
cin>>N>>r;
double *pointx, *pointy;
pointx = new double[N+1];
pointy = new double[N+1];
for(int a=0; a<N; a++){
cin>>pointx[a]>>pointy[a];
}
pointy[N]= pointy[0];
pointx[N] = pointx[0];
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
if(N==1){
perimeter=2*PI*r;
cout<<perimeter;

}
else{
if(N==2){
perimeter=2*(pow((pow((pointx[0]-pointx[1]),2)+pow((pointy[0]-pointy[1]),2)),0.5)) + 2*PI*r;
cout<<perimeter;

}
else{
double angle(0);
for(int a=0; a<N; a++){
perimeter += pow((pow((pointx[a]-pointx[a+1]),2)+pow((pointy[a]-pointy[a+1]),2)),0.5);
}

double p1x, p2x, p3x, p1y, p2y, p3y, m1, m2;

p1x=pointx[N-1]; p2x=pointx[0]; p3x=pointx[1];
p1y=pointy[N-1]; p2y=pointy[0]; p3y=pointy[1];
if(p3x==p2x)
m1=tan(PI/2.0);
if(p2x==p1x)
m2=tan(PI/2.0);
if(p2x!=p3x)
m1=(p3y-p2y)/(p3x-p2x);
if(p2x!=p1x)
m2=(p1y-p2y)/(p1x-p2x);
angle = 2*PI - (PI + fabs(atan(m1)-atan(m2)));
for(int a=1; a<N; a++){
p1x=pointx[a-1]; p2x=pointx[a]; p3x=pointx[a+1];
p1y=pointy[a-1]; p2y=pointy[a]; p3y=pointy[a+1];
if(p3x==p2x)
m1=tan(PI/2.0);
if(p2x==p1x)
m2=tan(PI/2.0);
if(p2x!=p3x)
m1=(p3y-p2y)/(p3x-p2x);
if(p2x!=p1x)
m2=(p1y-p2y)/(p1x-p2x);

angle += ((2*PI) - (PI + fabs(atan(m1)-atan(m2))));
}

perimeter += r*angle;
cout<<perimeter;
}}
delete pointx;
delete pointy;
return 0;}

Re: my program is correct, please tell me my error WA #4
Posted by mirzauzairbaig 15 Jan 2010 22:35
Please reply !!
Re: my program is correct, please tell me my error WA #4
Posted by tiancaihb 16 Jan 2010 12:48
3 1.2
12.24 13.34
0.00 24.75
-33.36 70.12


153.41

your program is too complicated to read
Re: my program is correct, please tell me my error WA #4
Posted by mirzauzairbaig 16 Jan 2010 13:51
I will tell you about my program. I am first calculating the distance between each point and summing it (perimeter). Then I am calculating the angle; of rope wound around each nail. I am adding the angles and then finding the total length by; perimeter + radius*angle. As my angle is in radians. Now, my answer is slightly above your answer in this test case; as I can see. But, if I change my angle to be always just 2 * PI * r, then I get it right !!

Now, first I can see the intuition for always setting angle to be 2*PI*r, but I cannot find any proof of why this will be always true. So, I am calculating it always for each nail. ( I think maybe, my calculation algorithm either gives a rounding error; or I am making a mistake)!!

Please do reply, and tell me why?
Re: my program is correct, please tell me my error WA #4
Posted by mirzauzairbaig 17 Jan 2010 03:46
Okay, I found my mistake. And the proof;(the reason) is got to do with exterior angles of a polygon sum up to 360 degrees! :)
thank you tianchb
Re: my program is correct, please tell me my error WA #4
Posted by tiancaihb 17 Jan 2010 10:17
Well, I suppose perhaps float is not accurate enough...
Since triangle functions in math.h are all float.
Congratulations anyway.