Не удается решить задачу с доброжелательным Никитой

Question

Очень доброжелательный Никита стоя в точке с координатами (0,0) посылает всем людям, стоящим в разных местах лучи добра, только вот он экономит лучи, поэтому те люди, которые находятся на одной прямой вполне наполнятся добротой за счет одного луча. Найдите минимальное количество лучей добра, если координаты всех людей, которым они предназначены, находятся в массиве a

Ввод:

a — координаты всех людей в виде [x1,y1,x2,y2,...,xn,yn], где 1<length(a)<22, length(a)%2==0

Вывод:

integer — минимальное количество лучей добра

get_result([1,1,5,5]) #1: все точки на одной прямой
get_result([2,2,-2,2,-2,-2,2,-2]) #4: нужно послать четыре луча, иначе никак

я смог написать функцию, для определения четверти, но дальше не могу ничего придумать

xcoord = int(input("введите х"))
ycoord = int(input("введите y"))
def quarter(xcoord, ycoord):
    if xcoord > 0 and ycoord > 0:
        print('I четверть')
    if xcoord > 0 and ycoord < 0:
        print('IV четверть')
    if xcoord < 0 and ycoord > 0:
        print('II четверть')
    if xcoord < 0 and ycoord < 0:
        print('III четверть')

print(quarter(xcoord, ycoord))

Answer 1

def quarter(x, y):
    if x==0:
        if y==0:
            return (1, 2, 3, 4)
        if y>0:
            return (1, 2)
        return (3, 4)
    if x>0:
        if y==0:
            return (1, 4)
        if y>0:
            return 1
        return 4
    if y==0:
        return (2, 3)
    if y>0:
        return 2
    return 3


inp = list(map(int, input().split()))
my_d = dict()

for x, y in zip(inp[::2], inp[1::2]): # каждому соотношению y/x записываем четверти, в которых находятся точки
    if 0 in (x, y):
        my_d[0] = my_d.get(0, []) + [quarter(x, y)]
    else:
        my_d[y/x] = my_d.get(y/x, []) + [quarter(x, y)]

beams = sum(len(set(my_d[k])) for k in my_d) # количество лучей
print(beams)

Answer 2

если необходимо учитывать не только четверть в которой находятся люди, но еще и то, стоят ли они на одной прямой, то можно воспользоваться формулой для расчета косинуса угла между векторами по координатам. тогда, если принять за базовый вектор вектор с координатами 0,1, получится что-то вроде этого:

def get_result(l):
    h1, h2 = set(), set()
    for i,j in zip(l[::2],l[1::2]):
        angl = {j/(i**2 + j**2)**.5}  # угол межу векторами
        if i < 0:
            h1 |= angl
        else:
            h2 |= angl
    return len(h1) + len(h2)
    
get_result([1,1,5,5]) # 1
get_result([2,2, -2,2, -2,-2, 2,-2])  # 4

так как угол между векторами лежит в диапазоне 0-180 градусов, проверяем условие i < 0 и складываем в множества h1 и h2 углы из обоих половин круга.

но здесь надо помнить про погрешность при вычислениях float, например, можно получить неожиданный результат:

get_result([5,5, 6,6])  # 2

хотя очевидно, что точки лежат на одной прямой. все потому, что в h2 получится {0.7071067811865475, 0.7071067811865476}

Answer 3

Можно обойтись без определения четверти в которой стоит человек. Другой подход - для луча проходящего через точку (x, y) определим ближайшую к нулю целую точку на этом луче (но не сам ноль). Если у двух лучей такие ближайшие точки совпадают, то совпадают и лучи. И наоборот, если ближайшие точки разные, то и лучи разные.

Ближайшая целая точка на луче вычисляется через НОД: g = gcd(x, y), x' = x / g, y' = y / g. Предполагается, что НОД положителен для аргументов любого знака. Случай x = 0, y = 0 надо будет обработать отдельно, так как НОД(0, 0) не определён. И в задаче у точки (0, 0) особый статус - через неё проходит любой никитин луч.

Функция key любому лучу сопоставляет ближайшую на луче целую точку. Начало координат обрабатывается отдельно:

def key(p):
    if p == (0, 0):
        return p
    x, y = p
    gcd = math.gcd(x, y)
    return x // gcd, y // gcd

Чтобы определить число уникальных лучей добра собираем ближайшие точки в множество. Начало координат требует отдельной обработки: если оно есть среди точек и кроме него есть другие точки, то один луч убираем:

def n_rays(a):
    s = set(map(key, zip(a[::2], a[1::2])))
    if (0, 0) in s and len(s) > 1:
        return len(s) - 1
    return len(s)

P.S. Этот ответ демонстрирует что задачу можно решить без вещественных чисел. Оба других ответа страдают от ошибок округления.

БЛОГ НА HUSL

Не удается решить задачу с доброжелательным Никитой

Ответы (3 шт):