1786 - NN

Cerinţa

Marele inginer NN, expert în construirea de baraje, a primit de data aceasta o sarcină mai îmbârligată. Acesta are de construit M baraje peste mai multe râuri dintr-o deltă și îşi planifică pe hârtie milimetrică construcţia fiecărui baraj în parte.

Toate râurile peste care are de construit baraje sunt braţe ale aceluiaşi fluviu şi toate pornesc din exact acelaşi punct pe lungimea fluviului. Pentru a-şi explica schiţa, NN marchează locul de despărţire a tuturor braţelor fluviului printr-un punct O, numit origine. Apoi, din origine pornesc N semidrepte, fiecare reprezentând o porţiune de uscat, astfel încât spaţiul gol dintre 2 semidrepte consecutive va fi considerat un braţ al fluviului.

După ce a desenat schiţa proiectului, NN se întreabă care e numărul de râuri pe care le acoperă complet fiecare baraj. Un baraj acoperă complet un râu dacă intersectează fiecare dintre malurile acestuia. Sarcina voastră este să îl ajutaţi oferindu-i informaţii precise pentru a-şi putea realiza planul cât mai eficient, păstrându-şi renumele.

Date de intrare

Pe prima linie a fișierului nn.in se află N și M, reprezentând numărul de semidrepte, respectiv numărul de baraje. Pe fiecare dintre următoarele N linii se vor afla informaţii despre cele N semidrepte, astfel: pe linia i (1<=i<=N) se află o pereche de numere naturale x și y, reprezentând coordonatele unui punct aflat pe semidreapta i (ştim deja că toate semidreptele pornesc din O(0, 0)). Pe fiecare dintre următoarele M linii se vor afla câte 4 numere x1, y1, x2, y2 reprezentând faptul că există un baraj care are extremităţile în punctele de coordonate x1 y1 și x2 y2.

Date de ieșire

În fișierul de ieșire nn.out se vor afișa M numere, fiecare pe o linie separată, reprezentând numărul de râuri blocate de fiecare dintre cele M baraje. În rezolvarea problemei nu se va ţine cont de grosimea barajului, aceasta fiind neglijabilă.

Restricţii şi precizări

Toate numerele din fișierul de intrare sunt naturale <= 10^5 Nici un punct din fișier nu coincide cu originea Pentru 10% din teste N = 2, M = 1 Pentru următoarele 20% din teste, capetele segmentelor (barajelor) se vor afla pe semidreptele din datele de intrare Pentru primele 50% din teste N, M <= 1000 Se recomandă folosirea long double pentru lucrul cu numere raționale!

Exemplu

nn.in

5 3 
5 1 

2 1 

2 5 

5 5 

0 4 

3 0 4 2 

1 4 3 1 

5 3 7 6

nn.out

1 


2 


0

Rezolvare

def read_input(filename):
    with open(filename, 'r') as file:
        N, M = map(int, file.readline().split())
        semilines = [tuple(map(int, file.readline().split())) for _ in range(N)]
        barrages = [tuple(map(int, file.readline().split())) for _ in range(M)]
    return N, M, semilines, barrages

def slope_intercept(point1, point2):
    x1, y1 = point1
    x2, y2 = point2
    if x1 == x2:
        slope = float('inf')
        intercept = x1
    else:
        slope = (y2 - y1) / (x2 - x1)
        intercept = y1 - slope * x1
    return slope, intercept

def count_blocked_rivers(semilines, barrage):
    x1, y1, x2, y2 = barrage
    count = 0
    for line in semilines:
        x3, y3 = line
        slope, intercept = slope_intercept((x1, y1), (x2, y2))
        if (y3 - slope * x3 - intercept) * (y1 - slope * x1 - intercept) < 0 and \
           (y3 - slope * x3 - intercept) * (y2 - slope * x2 - intercept) < 0:
            count += 1
    return count

def write_output(filename, results):
    with open(filename, 'w') as file:
        for result in results:
            file.write(str(result) + '\n')

def main():
    N, M, semilines, barrages = read_input('nn.in')
    results = []
    for barrage in barrages:
        results.append(count_blocked_rivers(semilines, barrage))
    write_output('nn.out', results)

if __name__ == "__main__":
    main()