ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1020. Ниточка

my program is correct, please tell me my error WA #4
Послано mirzauzairbaig 15 янв 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
Послано mirzauzairbaig 15 янв 2010 22:35
Please reply !!
Re: my program is correct, please tell me my error WA #4
Послано tiancaihb 16 янв 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
Послано mirzauzairbaig 16 янв 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
Послано mirzauzairbaig 17 янв 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
Послано tiancaihb 17 янв 2010 10:17
Well, I suppose perhaps float is not accurate enough...
Since triangle functions in math.h are all float.
Congratulations anyway.