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

Show all messages Hide all messages

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

Please reply !!
3 1.2
12.24 13.34
0.00 24.75
-33.36 70.12


153.41

your program is too complicated to read
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?
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
Well, I suppose perhaps float is not accurate enough...
Since triangle functions in math.h are all float.
Congratulations anyway.