Liczba trójkątów z N punktami wewnątrz

Question

Biorąc pod uwagę niektóre punkty w płaszczyźnie (do 500 punktów), brak 3 współliniowych. Musimy określić liczbę trójkątów, których wierzchołki pochodzą od podanych punktów i które zawierają dokładnie N punktów w nich. Jak skutecznie rozwiązać ten problem? Naiwny algorytm O (n^4) jest zbyt wolny. Jakieś lepsze podejście?

Answer 1

Można spróbować myślenia trójkąta jako punkt przecięcia trzech pół-przestrzeni. Aby znaleźć liczbę punktów wewnątrz trójkąta A, B, C najpierw rozważ zestaw punktów po jednej stronie nieskończonej linii w kierunku AB. Niech te zestawy L (AB) i R (AB) dla punktów z lewej i prawej. Podobnie to samo z innymi dwoma krawędziami i zestawami budującymi L (AC) i R (AC) oraz zestawami L (BC) i R (BC).

więc liczba punktów w ABC będzie liczba punktów przecięcia L (AB), L (AC) i L (BC). (Zamiast tego możesz rozważyć R (AB) w zależności od orientacji trójkąta).

Teraz, jeśli chcemy wziąć pod uwagę pełny zestaw 500 punktów. Najpierw weź wszystkie pary punktów AB i skonstruuj zestawy L (AB) i R (AB). Spowoduje to wykonanie operacji O (n^3).

Następny testujemy wszystkie trójkąty i znaleźć przecięcia trzech setach. Jeśli używamy jakiejś struktury tabeli mieszającej dla zestawów, to znalezienie punktów przecięcia jest jak wyszukiwanie hashtable. Jeśli L (AB) ma l elementów, L (AC) ma m elementów i L (BC) n elementów. Powiedz l> m> n. Dla każdego punktu w L (BC) musimy wykonać odnośnik w L (AC) i L (BC), tak aby maksymalnie 2n wyszukiwań hashtable.

Szybciej można rozważyć geometryczną tabelę odnośników. Podziel całą swoją domenę na grubą siatkę, powiedz 10 na 10. Możemy wtedy umieścić każdy punkt w zbiorze G (i, j). Następnie możemy podzielić zestawy L (AB) na każdą komórkę siatki. Powiedz wywołać te zestawy L (AB, i, j) i R (AB, i, j). Podczas testowania dla skrzyżowań najpierw ćwicz, które komórki siatki leżą w przecięciu. To znacznie zmniejsza przestrzeń poszukiwań, a ponieważ każdy zestaw L (AB, i, j) zawiera mniej członków, będzie mniej wyszukiwań związanych z hashtable.

Answer 2

Właściwie zdarzyło mi się napotkać podobny problem niedawno, ale jedyną różnicą było to, że było około 300 pkt i rozwiązać go za pomocą bitset (C++ STL). Dla każdej pary punktów, powiedzmy (x [i], y [i]) i (x [j], y [j]), utworzyłem bitset < 302> B [i] [j] i B [i] [j] [k] przechowuje 1, jeśli k-ty punkt znajduje się powyżej segmentu linii od punktu i do punktu j, w przeciwnym razie zapisałbym 0.

Teraz w sposób brutalny otrzymuję trzy punkty, aby utworzyć trójkąt, powiedzmy (x [i], y [i]), (x [j], y [j]) i (x [k], y [k]), wtedy punkt, powiedzmy z-tego punktu, byłby wewnątrz trójkąta, gdy B [i] [j] [z] == b [b] [j] [k] & & B [j] [k] [z] == B [j] [k] [I] & & B [k] [i] [z] == B [k] [i] [j], ponieważ punkt wewnątrz trójkąta byłby podobny do znaku bok trójkąta jako trzeci punkt trójkąta (który nie znajduje się po tej stronie). Dostaję więc trzy zmienne bitsetowe P = B [i] [j], Q = B [j] [k] i R = B [k] [i] i tam przyjmowanie bitów ORAZ zastosowanie funkcji count() do podania mi aktywną liczbę bitów, a więc liczbę punktów w trójkącie. Ale upewnij się, że zmieniasz zmienną P w taki sposób, że daje ona B [i] [j] [k] = 1, jeśli nie bierze bitowego nie (~) tej zmiennej.

Chociaż powyższe rozwiązanie jest problematyczne, mam nadzieję, że pomoże. To jest związek problemów: http://usaco.org/current/index.php?page=viewproblem&cpid=660