Форум программистов, компьютерный форум CyberForum.ru

Голодная коза на веревке. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 12:30     Голодная коза на веревке. #1
Есть квадратное поле с травой, сторона квадрата - N.
В центре поля привязана веревка длины r. К другому концу веревки привязана коза.
Коза поедает всю траву, до которой может дотянуться, при этом ей мешает длина веревки.
Ввод: В первой строке файла input содержатся два целых числа N и r через пробел.
1<=N,r<=100
Ограничения: время счета - 1 сек, объем памяти: 16 Mb
Вывод: С точностью до 3-ех знаков указать площадь травы, которую cъест коза.

Пример:
INPUT:
10 6
OUTPUT:
95.091

http://acm.timus.ru/problem.aspx?space=1&num=1084
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Darky
Быдлокодер
 Аватар для Darky
507 / 294 / 45
Регистрация: 22.11.2009
Сообщений: 892
Завершенные тесты: 1
08.01.2010, 12:43     Голодная коза на веревке. #2
Если я правильно понимаю, то нужно посчитать площадь круга с заданным радиусом? При некоторых условиях
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 12:48  [ТС]     Голодная коза на веревке. #3
Веревка, вытянутая на полную длину образует круг.
Поле образует квадрат.
Пусть S - это искомая площадь.
Имеем три случая:

1) Край круга не достает до стороны квадрата.
r<=N/2
S= площадь круга = PI*r^2

2) Край круга протирается дальше чем углы квадрата
Пусть N2 - расстояние от центра квадрата до угла квадрата.
N2= sqrt( 0.5*N^2 )= N/sqrt( 2.0 )
Условие: r>=N2
S= площадь квадрата = N^2

3) Край круга находится дальше чем сторона квадрата, но меньше чем угол квадрата.
Условие:
N/2<r<N2
Осталось посчитать площадь в этом самом сложном случае
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 13:02     Голодная коза на веревке. #4
http://amway.ucoz.ua/pusti_kozla_v_ogorod.rar

Вот, если это вам поможет))
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 13:05  [ТС]     Голодная коза на веревке. #5
Не - будем без подсказок решать
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 13:08     Голодная коза на веревке. #6
стоп, так эт я написал, или вы мне не доверяете?

Добавлено через 1 минуту
там просто выкладки на А4 по поиску площади 4-ех секторов и 4-ех треугольников, с рисунком
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 13:08  [ТС]     Голодная коза на веревке. #7
Вывод long double с используя printf()
Этот код тоже ты написал ?
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 13:10     Голодная коза на веревке. #8
хотя, нет, в суме 2*А4 + финальная формула на 3-ем листе

Добавлено через 52 секунды
я старался расписать так, что-бы можно было найти ошибку
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16821 / 5242 / 318
Регистрация: 30.03.2009
Сообщений: 14,118
Записей в блоге: 26
08.01.2010, 13:10     Голодная коза на веревке. #9
Цитата Сообщение от odip Посмотреть сообщение
3) Край круга находится дальше чем сторона квадрата, но меньше чем угол квадрата.
Условие:
N/2<r<N2
Осталось посчитать площадь в этом самом сложном случае
Это есть площадь круга минус учетверённая площадь сегмента (который торчит из-за сторон квадрата). Радиус известен, угол вычисляется, соотвеnственно вычисляется площадь сегмента
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 13:16     Голодная коза на веревке. #10
Evg, а если решить еще и через площади сегментов, тогда если формулы сойдутся - я вывел верно, иначе, ищем ошибку..

Добавлено через 3 минуты
odip, я же говорил, ошибка в последнем знаке - это ронг ансер..
Delphin_KKC
UNIX-way
 Аватар для Delphin_KKC
710 / 494 / 17
Регистрация: 15.01.2009
Сообщений: 1,721
08.01.2010, 13:21     Голодная коза на веревке. #11
Цитата Сообщение от odip Посмотреть сообщение
Веревка, вытянутая на полную длину образует круг.
Поле образует квадрат.
Пусть S - это искомая площадь.
Имеем три случая:

...

2) Край круга протирается дальше чем углы квадрата
Пусть N2 - расстояние от центра квадрата до угла квадрата.
N2= sqrt( 0.5*N^2 )= N/sqrt( 2.0 )
Условие: r>=N2
S= площадь квадрата = N^2
...
Для этого случая формула такая:
2) Край круга протирается дальше чем углы квадрата
Пусть N2 - расстояние от центра квадрата до угла квадрата.
N2= sqrt((0.5*N)^2+(0.5*N)^2)=0.5*N*sqrt(2.0) //по т.Пифагора
Условие: r>=N2
S= площадь квадрата = N^2
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 13:26  [ТС]     Голодная коза на веревке. #12
Delphin_KKC, можешь сам убедиться что 0.5*sqrt(2.0) == 1/sqrt( 2.0 )
)))
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 13:27     Голодная коза на веревке. #13
odip, согласен, с 1/sqrt(2.0)
Delphin_KKC
UNIX-way
 Аватар для Delphin_KKC
710 / 494 / 17
Регистрация: 15.01.2009
Сообщений: 1,721
08.01.2010, 13:37     Голодная коза на веревке. #14
Цитата Сообщение от odip Посмотреть сообщение
Delphin_KKC, можешь сам убедиться что 0.5*sqrt(2.0) == 1/sqrt( 2.0 )
)))
Может быть. Я формулу писал прямо в окне ответа.
Но умножение, насколько я помню из уроков ассемблера, выполняется чуть быстрее деления.
А в задаче есть ограничение по времени счёта.

Для ещё большего ускорения можно вместо 0.5*sqrt(2.0) написать 0.707 (на всякий случай проверьте константу; ибо по памяти пишу)
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 15:21  [ТС]     Голодная коза на веревке. #15
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/* Thread 83603 */
 
#include <stdio.h>
#include <assert.h>
#include <math.h>
 
 
/********************************************************************/
#define PI 3.141592653589793238462
 
 
/********************************************************************/
double calc_koza_square( double N, double r );
 
 
/********************************************************************/
int main( void ) {
 
int N_int, r_int;
double S;
 
 
freopen( "input.txt", "r", stdin );
freopen( "output.txt", "w", stdout );
 
scanf( "%d %d", &N_int, &r_int );
assert( 1<=N_int && N_int<=100 );
assert( 1<=r_int && r_int<=100 );
 
S= calc_koza_square( (double)N_int, (double)r_int );
printf( "%.3f\n", S );
 
return 0;
 
} /* main() */
 
 
/********************************************************************/
double calc_koza_square( double N, double r ) {
 
double N_2, N2, teta, S;
 
 
N_2= 0.5*N;
N2= N/sqrt( 2.0 );
 
if ( r<=N_2 ) {
    return PI*r*r;
} else if ( r>=N2 ) {
    return N*N;
}
 
teta= 2*acos( N_2/r );
S= PI*r*r-4*(0.5*r*r*(teta-sin(teta)));
 
return S;
 
} /* calc_koza_square() */
Во - правильно считает.

Добавлено через 10 минут
teta - угол сегмента, который торчит за пределы квадрата.

Найдем половину этого угла.
cos( teta/2 ) = катет / гипотенузу = N/2 / r

teta= 2*acos( N_2/r )

Площадь_сегмента = 0.5*r*r*(teta-sin(teta))

S= площадь_круга - 4*площади_сегмента = PI*r*r-4*(0.5*r*r*(teta-sin(teta)))

Добавлено через 1 минуту
outoftime, чего-то сильно перемудрил у себя в файле rtf

Добавлено через 1 час 18 минут
Задача Пуговицы - Игра Пуговицы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2010, 15:22     Голодная коза на веревке.
Еще ссылки по теме:

ВОЛК, КОЗА, КАПУСТА
Мальчик вращает камень, привязанный к веревке длиной 1м, в вертикальной плоскости с частотой 12 гц
Волк заяц и коза C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 15:22     Голодная коза на веревке. #16
сейчас проферю hosts, может вируса..
Yandex
Объявления
08.01.2010, 15:22     Голодная коза на веревке.
Ответ Создать тему
Опции темы

Текущее время: 05:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru