|
Охотник
(Время: 1 сек. Память: 16 Мб Сложность: 27%)
Для решения этой задачи можно перебрать все мишени и подсчитать для каждой из них количество других мишеней, которые могут быть поражены одним выстрелом при стрельбе по ней. Т.е. для каждой мишени (x,y) следует вычислить общее количество мишеней, лежащих на луче (0,0)-(x,y). Максимальное такое значение и будет ответом на задачу.
Точки (x1,y1) и (x2,y2) будут располагаться на одной линии с охотником, когда y1/x1=y2/x2 (тангенсы угла наклона совпадают). Во избегании возможных ошибок, связанных с делением на ноль, следует вышеупомянутое условие преобразовать к виду x2*y1=x1*y2. Так же следует учесть, что нужно проверять принадлежность мишеней одному лучу, а не прямой. Для проверки последнего можно сравнить знаки мишеней по координатам, т.е. проверить условия x1*x2>=0 и y1*y2>=0.
Алгоритмическая реализация вышеописанного:
read(n)
m=0
for i=1..n{
read(x[i],y[i])
c=1
for j=1..i-1
if(x[i]*y[j]=x[j]*y[i] and x[i]*x[j]>=0 and y[i]*y[j]>=0) c=c+1
if(c>m) m=c
}
write(m)
| |
