Sper sa fie vacanta de vina pentru numarul mic de rezolvitori, desi
din cate va cunosc pot sa bag mana in foc ca nu puteti suferi
geometria analitica :) Ideea rezolvarii pleaca de la observatia ca
bucata vizibila dintr-o dreapta este intotdeauna o multime
compacta, adica fie multimea vida, fie un singur interval. Deci nu
pot trasa un sistem de drepte astfel incat pe dreapta D sa apara
doua segmente vizibile din P, iar bucata dintre segmente sa nu fie
vizibila. Si atunci ce am de facut? Iau pe rand fiecare dreapta si
o consider initial vizibila in intregime. Apoi intersectez dreapta
cu fiecare din celelalte drepte si decupez bucatile invizibile.
Daca in final ramane un segment vizibil, dreapta este observabila.
Daca ramane un singur punct vizibil sau nici atat, dreapta nu este
observabila.

Cum facem decuparea? Sa ne inchipuim ca dreapta de analizat ar fi
chiar axa Ox. Atunci as putea retine la fiecare moment doua numere,
Xmin si Xmax, extremitatile segmentului vizibil de pe dreapta (initial
Xmin=-inf, Xmax=+inf). Intersectand pe rand fiecare dreapta cu axa Ox,
calculez coordonata punctului de intersectie si vad daca Xmin si Xmax
trebuie actualizate. A se vedea jpg-ul de mai jos:



----------+-----------          Xmin=-inf       Xmax=+inf
          0
                 *P

        /
      /
----/-----+-----------          Xmin=-6         Xmax=+inf
  /       0
                 *P


        /      \
      /          \
----/-----+--------\--          Xmin=-6         Xmax=+9         etc.
  /       0          \
                 *P

Daca in final Kmin<Kmax inseamna ca a ramas o bucatica vizibila din
Ox, care este deci observabila.

Cazul particular cand gasim o alta dreapta paralela cu Ox il vom
analiza mai jos. Acum sa generalizam si sa ne intrebam ce facem daca
dreapta de analizat este una oarecare de ecuatie (D): Ax+By+C=0. Ideea este
sa *parametrizam* aceasta dreapta D, adica sa fixam pe ea o origine
si sa ii scriem ecuatia functie de un parametru K care sa parcurga
toata multimea R (pentru axa Ox, parametrul era chiar x).

Originea (X0, Y0) o aflam usor, de exemplu luand Y0=0 si, conform ecuatiei
de mai sus, X0=-C/A. Asta pentru ca (X0, Y0) trebuie sa fie pe dreapta, deci
A*X0+B*Y0+C=0. Daca A=0, atunci luam X0=0 si Y0=-C/B. Nu se poate ca A si B
sa fie simultan 0, daca la asta va ganditi :)

Parametrizarea o facem scriind C=-A*X0-B*Y0 si inlocuind in ecuatia
generala a dreptei:

A*x+B*y-A*X0-B*Y0=0 ==> A(x-X0)+B(y-Y0)=0, sau:

x-X0   y-y0
---- = ---- = K, unde pe K l-am introdus din burta. Acum se observa ca
  B     -A

daca ii dam lui K valori de la -inf la +inf obtinem o multime de
puncte de coordonate x=X0+K*B, y=Y0-K*A, toate verificand ecuatia
dreptei D si toate distincte, deci descriind exact dreapta D. In
particular, cand K=0 obtinem x=X0, y=Y0, adica originea fixata.
Initial toate punctele de pe dreapta sunt vizibile, ceea ce se exprima
parametric Kmin=-inf, Kmax=+inf.

Dupa ce am parametrizat cu bine dreapta (pas care in program se reduce
la a afla X0 si Y0), ne apucam sa o intersectam cu fiecare din
celelalte drepte si sa ajustam valorile pentru Kmin si Kmax. Fie deci
o alta dreapta, (D'): A'x+B'y+C'=0. Atunci:

A) Daca AB'=A'B, atunci dreptele sunt paralele si inseamna ca fie D'
se interpune intre P si D, pe care o obtureaza complet, fie D se
interpune intre D' si P si atunci D' nu ma deranjeaza cu nimic. Cum
verific cine unde se interpune ? Cel mai simplu este sa observam ca D'
se interpune intre P si D daca si numai daca originea (X0',Y0') a
dreptei D' se afla de aceeasi parte a lui D cu punctul P (Nu uitati,
am presupus D si D' paralele).

B) Daca AB'<>A'B, atunci D si D' se intersecteaza. Aflam punctul de
intersectie (Xi, Yi) prin rezolvarea sistemului:

{ A x  + B y + C = 0
{ A'x  + B'y + C = 0

Apoi aflam *parametrul* punctului de intersectie pe dreapta D, Ki, cu
una din formulele Ki=(Xi-X0)/B sau Ki=(Yi-Y0)/(-A), dupa cum A sau B
sunt 0. Este clar ca exact unul din segmentele de pe dreapta (-inf,
Ki] sau [Ki, inf) este obturat. Cum aflu care? Cel mai simplu este sa
vad daca dreapta D' imi ascunde sau nu punctul (Xi1,Yi1) de parametru
Ki+1. Adica: Xi1=X0+(Ki+1)*B, Yi1=Y0-(Ki+1)*A, si daca (Xi1, Yi1) se
afla de aceeasi parte a lui D' cu punctul P, atunci segmentul [Ki,
inf) este vizibil, altfel segmentul (-inf, Ki] este vizibil. Vezi poza.

                            / K->inf
                          /                    (Xi1,Yi1) este vizibil
                        - Kmax                 din P pentru ca cele doua
             (Xi1,Yi1)/                        puncte se afla de aceeasi
        D'*         - Ki+1                     parte a lui D'. Asadar
             *    /                            [Ki, inf) este neobturat
        (Xi,Yi) # Ki              * P          de D'.
              /    *
            /         *
          /              *
        - Kmin
    D /
    / K-> -inf

B1) Daca segmentul [Ki, inf) este vizibil, avem cazul:

Kmin                           Kmax
  +-----------------------------+              (ceea ce se vede inca din D)
               +-------------------------...   (ceea ce nu este obturat
               Ki                         inf   de dreapta D')

               +----------------+              (ceea ce ramane vizibil)
          noul Kmin            Kmax

Deci actualizarea este: Kmin:=max(Kmin, Ki)

B2) Similar, daca vizibil este (-inf, Ki], atunci actualizarea de
facut este: Kmax:=min(KMax, Ki)

Ca urmare, Kmin creste tot timpul, iar Kmax scade tot timpul. Daca in
final Kmin<Kmax, atunci dreapta D este observabila.

Ar mai trebui spus ca doua puncte (X1,Y1) si (X2,Y2) se afla de
aceeasi parte a dreptei (D): Ax+By+C=0 daca si numai daca expresiile
A*X1+B*Y1+C si A*X2+B*Y2+C au acelasi semn.