Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
13 / 13 / 9
Регистрация: 28.07.2017
Сообщений: 103

Кот ученый - достает ли прямая до заданного отрезка на плоскости

25.02.2018, 22:45. Показов 2280. Ответов 28

Студворк — интернет-сервис помощи студентам
Здравствуйте. Решал задачу и столкнулся с проблемой, что не все тесты проходят.

Условие:
Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной l, n рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем k рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба (0, 0).

Входные данные:
В первой строке находятся числа l, n, k. Далее идет n строк: координаты головы (x1i, y1i) и хвоста (x2i, y2i) каждой рыбины. Все входные данные - целые числа, не превышающие по модулю 100.

Выходные данные:
Вывести день, на который у кота появится чувство голода.

Вот код:
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <cmath>
 
bool ableToEat (int x1, int y1, int x2, int y2, int l);
 
int main()
{
    int l, qFish, quant;
    std::cin >> l >> qFish >> quant;
    
    int able = 0;
    for (int i = 0; i < qFish; ++i)
    {
        //input x and y
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        if (ableToEat (x1, y1, x2, y2, l))
        {
            ++able;
        }
    }
    std::cout << ((able % quant == 0) ? (able / quant) : (able / quant + 1)) << std::endl;
    return 0;
}
 
bool ableToEat (int x1, int y1, int x2, int y2, int l)
{
    //sides
    float a = std::hypot(x1, y1);
    float b = std::hypot(x2, y2);
    //fund
    float c = std::hypot(x1 - x2, y1 - y2);
    //half of triangle perimeter
    float p = (a + b + c) / 2;
    //square of a triangle
    float s = sqrt(p * (p - a) * (p - b) * (p - c));
    //height
    float hght = 2 * s / c;
    if (a * a + c * c < b * b || b * b + c * c < a * a)
    {
        if (a <= l || b <= l)
        {
            return true;
        }
    }
    else if (hght <= l)
    {
        return true;
    }
    return false;
}


Подскажите, пожалуйста, в чем может быть проблема.
Заранее благодарю.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
25.02.2018, 22:45
Ответы с готовыми решениями:

Указать, каким четвертям координатной плоскости принадлежат точки заданного отрезка
Даны вещественные числа x1, y1, x2, y2. Указать, каким четвертям координатной плоскости принадлежат точки отрезка с концами (x1,y1) и...

Прямая на плоскости и прямая в пространстве
Помогите пожалуйста решить, + желательно как их решать. 1) 16x^2+25y^2+32x-100y-284 = 0 2) y+2z^2 = 6x^2 + Построить график.

Wi-Fi сигнал достает до улицы, но не достает до соседней комнаты
В общем, проблема озвучена в заголовке, прошу разъяснить, в чем может быть проблема и, по возможности, пути ее решения. Вот несколько...

28
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
28.02.2018, 00:20
Студворк — интернет-сервис помощи студентам
А если до головы дотянется, то че уже не съест что ли?
Вообще меня всегда бесила в задачах по программированию то, что условия ставятся очень расплывчато.

Надо четко тогда
Цитата Сообщение от outoftime Посмотреть сообщение
Возьмем лимит в операций, если мы будет пробегать по всем прямым, делим на 100. В рузультате отрезок [-100, 100] делим на частей пробегаем по всем значениям x если в какой либо точке растояние до центра меняется с на значит отрезок пересекает окружность. Точность выходит
Зачем пробегать по всем прямым? Круг это выпуклое множество, а значит достаточно проверить, что хотя бы один из двух концов рыбы принадлежит этому кругу.
1
13 / 13 / 9
Регистрация: 28.07.2017
Сообщений: 103
28.02.2018, 00:37  [ТС]
Просто Саша, Выпуклое, т.е. хвост и голова могут быть вне окружности, а тело - в окружности.
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
28.02.2018, 01:21
Если хвост или голова принадлежат кругу, то ответ положителен.
Если оба не принадлежат, то считаем расстояние от точки до прямой определяемой этими двумя точками.
Если это расстояние не больше R - ответ положительный.
0
13 / 13 / 9
Регистрация: 28.07.2017
Сообщений: 103
28.02.2018, 01:39  [ТС]
Просто Саша, не совсем. Нужно еще учесть условие, что отрезок может быть , например, намного выше по оси y чем окружность, причем, если из отрезка сделать прямую, то он будет пересекать окружность. В результате имеем недостижимый отрезок, и ответ, который говорит, что достичь отрезка можно.

Похожая идея реализована (видимо, частично) в шапке темы.
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
28.02.2018, 09:07
Цитата Сообщение от dude78 Посмотреть сообщение
не совсем. Нужно еще учесть условие, что отрезок может быть , например, намного выше по оси
Нет, совсем. Если это непонятнно, то открываем учебник по геометрии и читаем темы:
1) Условия пересечения прямой и окружности
2) Расстояние от точки до прямой.
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
28.02.2018, 12:52
Цитата Сообщение от Просто Саша Посмотреть сообщение
то считаем расстояние от точки до прямой определяемой этими двумя точками.
Если это расстояние не больше R - ответ положительный.
От какой точки? От центра круга?
Тогда так. Берите карандаш и лист бумаги. Оси (чтоб мне удобнее было командовать). Круг с центром (0,0) радиуса R=1.
Точка А( 8, 0) и В(5, 0). Нарисовали?
Теперь подсчитайте расстояние от центра до прямой АВ. Сколько получилось? Правильно, у меня тоже 0. Оно больше R? Кажется, нет. Или вы другого мнения?
Ваши выводы?
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
28.02.2018, 23:00
Цитата Сообщение от Байт Посмотреть сообщение
От какой точки? От центра круга?
Ладно, вникать в ваши доводы не стану, но признаю, что у меня была допущена небольшая ошибка.

Алгоритм вот такой:
1) Проверить не принадлежит ли хотя бы один конец отрезка заданной окружности. Если да - ответ положительный.
2) Если оба конца лежат вне данной окружности, провести к прямой, определяемой этими концами перпендикуляр и проверить, лежит ли основание этого перпендикуляра внутри круга и лежат ли концы отрезка в разных полуплоскостях, которые определяются данным перпендикуляром. Если да - ответ положительный.

Добавлено через 11 минут
Иными словами, второй пункт можно заменить следующим:
Проверить принадлежит ли основание перпендикуляра, проведенного из центра окружности к прямой, определяемой концами отрезка как самой окружности, так и данному отрезку. Если да ответ положительный.
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
01.03.2018, 01:11
Цитата Сообщение от Просто Саша Посмотреть сообщение
вникать в ваши доводы не стану,
И не надо. Зачем они вам?
Цитата Сообщение от Просто Саша Посмотреть сообщение
Если да ответ положительный.
Только пургу нести не надо. Не надо говорить о вещах, в которых вы ничего не понимаете. Или понимаете мало. Мне то плевать. Но тут же вас неразумные дети могут послушать.
Цитата Сообщение от Просто Саша Посмотреть сообщение
Проверить принадлежит ли основание перпендикуляра, проведенного из центра окружности к прямой, определяемой концами отрезка как самой окружности, так и данному отрезку.
Интересно, как вы себе это представляете?
Я очень рад, что эта задача произвела некоторые шевеления в вашей голове. Но пока эти шевеления не заслуживают ни анализа, ни опровержения. Ибо это пустое бормотание и больше ничего.
Поймите меня правильно. Если бы мы были с вами здесь вдвоем, я бы просто молча ушел. Но тут же люди, неопытные, и могут подумать, что вы говорите нечто осмысленное.
0
13 / 13 / 9
Регистрация: 28.07.2017
Сообщений: 103
18.03.2018, 00:52  [ТС]
Байт, outoftime, It is an old maxim of mine that when you have excluded the impossible, whatever remains, however improbable, must be the truth - Цитата. Иными словами, я пробовал решить через скалярное произведение, используя данную статью. Но ничего не вышло. Тогда я уже начал подумывать, а праильно ли у меня сделан вывод ответа. Прочел условие, и пришел к выводу, что скорее всего вывод ответа у меня сделан не правильно. Сделал его правильным и количество проходимых тестов увеличилась. Тогда я взял тест с наибольшей проходимостью (т.е. тот, что в шапке темы) и изменил вывод ответа. Результат - 100%.

Зашел сюда и увидел, что у 13-го поста 69% пройдено перебором. Посмотрел, и вывод то ответа там был правильным, т.е.
Цитата Сообщение от outoftime Посмотреть сообщение
(1 + available / k)
Он отличался от того, что в шапке, но я почему-то на это не обратил внимания.

Исходный код:
Кликните здесь для просмотра всего текста
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
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
#include <cmath>
 
bool ableToEat (int x1, int y1, int x2, int y2, int l);
 
int main()
{
    int l, qFish, quant;
    std::cin >> l >> qFish >> quant;
 
    int able = 0;
    for (int i = 0; i < qFish; ++i)
    {
        //input x and y
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        if (ableToEat (x1, y1, x2, y2, l))
        {
            ++able;
        }
    }
    std::cout << able / quant + 1 << std::endl;
    return 0;
}
 
bool ableToEat (int x1, int y1, int x2, int y2, int l)
{
    //sides
    float a = std::hypot(x1, y1);
    float b = std::hypot(x2, y2);
    //fund
    float c = std::hypot(x1 - x2, y1 - y2);
    //half of triangle perimeter
    float p = (a + b + c) / 2;
    //square of a triangle
    float s = sqrt(p * (p - a) * (p - b) * (p - c));
    //height
    float hght;
    if (c <= 0)
    {
        if (a <= l)
        {
            return true;
        }
        return false;
    }
    else
    {
        hght = 2 * s / c;
    }
    if (a * a + c * c < b * b || b * b + c * c < a * a)
    {
        if (a <= l || b <= l)
        {
            return true;
        }
    }
    else if (hght <= l)
    {
        return true;
    }
    return false;
}


Спасибо! .
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
18.03.2018, 00:52

Требуется программа для построения отрезка по двум точкам на плоскости ХОУ и далее, из одного из концов построенного отрезка построить второй отрезок
Требуется программа для построения отрезка по двум точкам на плоскости ХОУ и далее, из одного из концов построенного отрезка построить...

Прямая на плоскости
1. Через точку C(C1, C2) провести прямую так, чтобы она отсекала от координатного угла равнобедренный треугольник. Использовать уравнение...

Прямая на плоскости
Даны уравнения двух сторон треугольника 2x-y=0, 5x-y=0 и уравнение 3x-y=0 одной из его медиан.

Прямая на плоскости
Через точку M(5,2) провести прямую отсекающий уровне вижризкы на осях кординат

Доказать, что прямая не пересекает отрезка, ограниченного данными точками
Доказать, что прямая 2x-3y+6=0 не пересекает отрезка, ограниченного точками M1(-2; -3), M2(1; -2). Пожалуйста, максимально обоснуйте...


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

Или воспользуйтесь поиском по форуму:
29
Ответ Создать тему
Новые блоги и статьи
Теория всего 12. ВГК
anaschu 21.07.2026
### Главные семантические изменения и дешифровка новой физики 1. **`REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`)**: Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .
Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание
Hrethgir 21.07.2026
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .
Теория всего 11. Основные параметры
anaschu 21.07.2026
Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .
Теория всего 10. Клод трусишка
anaschu 21.07.2026
Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
Теория всего 9. Окончательная проработка метафоры "дерево = традиции"
anaschu 21.07.2026
Скрытые параметры ядра ОДУ: Механика Глубинного Рока Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .
Теория всего 8. Clauude трусишка. Ответ джемени
anaschu 21.07.2026
Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .
Теория всего 7. Дерево - это патриархат, грибы - это феминизм
anaschu 21.07.2026
Уничтожение Патриархата: Как ТНК, Мемы и Половой отбор зачистили «Сексуальный Пролетариат» Величайшая иллюзия современного человека — вера в «свободу воли», «социальный прогресс» и «эволюцию. . .
История и социология Терры на примере борьбы микориз за пространство. 1. Глоссарий терры.
anaschu 21.07.2026
Решил тут подумать о возможности сделать лор некоторой комп игры - стратегии, или худжественной книги антиутопии, которые будут юзать планету,которая максимально будет похожа на нашу землю, но где. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru