Задача
Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.
Входные данные
В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.
Выходные данные
Вывести день, на который у кота появится чувство голода.
Тесты
| Входные данные | Выходные данные |
| [latex]4\, 4\, 2[/latex] | [latex]2[/latex] |
| [latex]1\, 1\, -1\, 3[/latex] | |
| [latex]2\, 2\, 4\, 2[/latex] | |
| [latex]-3\, -4\, -3\, 4[/latex] | |
| [latex]1\, -5\, 4\, -4[/latex] | |
| [latex]3\, 2\, 1[/latex] | [latex]3[/latex] |
| [latex]1\, 2\, 3\, 4[/latex] | |
| [latex]1\, -1\, -1\, 1[/latex] | |
| [latex]3\, 5\, 4[/latex] | [latex]1[/latex] |
| [latex]2\, 4\, 5\, 7[/latex] | |
| [latex]1\, -1\, -1\, 1[/latex] | |
| [latex]8\, 10\, 2\, 7[/latex] | |
| [latex]12\, 3\, 4\, 2[/latex] | |
| [latex]100\, 100\, -100\, -100[/latex] |
Код программы
|
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 |
#include <iostream> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int l, n, k, count=0; cin >> l >> n >> k; for(int i=0; i<n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l) count++; else { int a, b, c; int deltaX=x2-x1; int deltaY=y2-y1; a=deltaY; b=-deltaX; c=y1*deltaX-x1*deltaY; if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1))) count++; } } cout << count/k+1 << endl; return 0; } |
Решение задачи
Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.
Ссылки
Условие задачи на e-olymp
Код решения