Wyobraź sobie kilka prostokątów narysowanych w płaszczyźnie, każdy prostokąt z wierzchołkami o współrzędnych całkowitych i bokami równoległymi do osi:
Prostokąty dzielą płaszczyznę na kilka rozłącznych regionów, które mają kolor czerwony i niebieski poniżej:
Twoim celem jest znalezienie liczby takich regionów, które są idealnymi kwadratami. W powyższym przykładzie są trzy:
Zauważ, że duży kwadrat pośrodku nie jest liczony, ponieważ nie jest to pojedynczy region, ale składa się z kilku mniejszych, niepowiązanych regionów.
Wkład
Możesz napisać funkcję lub pełny program dla tego wyzwania.
Dane wejściowe będą 4n
nieujemnymi liczbami całkowitymi definiującymi n
prostokąty w płaszczyźnie. Każdy prostokąt jest reprezentowany przez dwa przeciwstawne wierzchołki, np. 4 9 7 8
Reprezentuje prostokąt z przeciwległymi wierzchołkami (4, 9)
i (7, 8)
. Zauważ, że ten prostokąt można również przedstawić jako 7 8 4 9
lub 4 8 7 9
.
Dokładny format wejściowy jest elastyczny (np. Ciąg oddzielony spacją, ciąg oddzielony przecinkami, pojedyncza tablica liczb całkowitych, lista krotek współrzędnych itd.), Ale bądź rozsądny i podaj przykład, jak uruchomić kod w poście. Nie możesz zmienić kolejności danych wejściowych.
Dla uproszczenia można założyć, że żadne dwie krawędzie nie będą się pokrywać - dotyczy to także nakładania się na wierzchołek. W szczególności oznacza to, że żadne dwa prostokąty nie będą się stykać od krawędzi do krawędzi lub od narożnika do narożnika, a prostokąty będą miały niezerowe pole.
Wydajność
Twój program powinien wydrukować lub zwrócić pojedynczą liczbę całkowitą, czyli liczbę kwadratowych regionów.
Punktacja
To jest kod golfowy, więc kod w najmniejszej liczbie bajtów wygrywa.
Przypadki testowe
Wkład:
0 0 5 5
6 8 10 4
14 16 11 13
19 1 18 2
Wydajność:
4
To po prostu cztery rozłączne kwadraty:
Wkład:
2 1 3 11
1 10 5 19
6 10 11 3
8 8 15 15
13 13 9 5
15 1 19 7
17 19 19 17
Wydajność:
3
To jest przykładowy przypadek testowy na początku postu.
Wkład:
0 9 15 12
6 3 18 15
9 6 12 20
13 4 17 8
Wydajność:
7
Wkład:
5 9 11 10
5 12 11 13
6 8 7 14
9 8 10 14
13 8 14 9
13 10 14 14
Wydajność:
14
Wkład:
0 99999 100000 0
Wydajność:
0
To tylko jeden duży prostokąt.
Wkład:
0 99999 100000 0
2 1 142857 285714
Wydajność:
1
Dwa duże prostokąty, które zachodzą na siebie.
Python 2,
480 436 386352 bajtyPobiera listę par współrzędnych przez STDIN w formacie:
i drukuje wynik do STDOUT.
Rzeczywistym programem, po zamianie łańcucha, jest:
Wyjaśnienie
Zamiast bawić się skomplikowanymi wielokątami, ten program zajmuje się prostymi segmentami linii. Dla każdego prostokąta wejściowego dodajemy każdą z czterech krawędzi osobno do listy segmentów zbiorczych. Dodanie segmentu do listy przebiega następująco: testujemy każdy z istniejących segmentów pod kątem przecięcia z nowym segmentem; jeśli znajdziemy skrzyżowanie, dzielimy oba segmenty w punkcie przecięcia i kontynuujemy. Aby to ułatwić, w rzeczywistości prowadzimy dwie oddzielne listy segmentów: horyzontalną i pionową. Ponieważ segmenty nie zachodzą na siebie, segmenty poziome mogą przecinać tylko segmenty pionowe i odwrotnie. Co więcej, oznacza to, że wszystkie przecięcia (nie biorąc pod uwagę krawędzi tego samego prostokąta) są „właściwe”, tj. Nie mamy przecięć w kształcie litery T, więc „obie strony” każdego segmentu są naprawdę podzielone.
Po zbudowaniu listy segmentów zaczynamy odliczać kwadraty. Dla każdej kombinacji czterech segmentów (szczególnie dwóch segmentów poziomych i dwóch pionowych) sprawdzamy, czy tworzą one kwadrat. Ponadto sprawdzamy, czy żaden wierzchołek nie leży w tym kwadracie (co może się zdarzyć, jeśli na przykład mamy mały kwadrat w większym). To daje nam pożądaną ilość. Należy pamiętać, że mimo iż program testuje każdą kombinację cztery razy w różnych zamówieniach, to szczególne uporządkowanie współrzędnych segmentu gwarantuje, że każde kwadraty liczymy tylko raz.
źródło
itertools
pętli, ale skończyło się to na dłuższym czasie. Mogę ogolić kilka bajtów za pomocąexec
zamiany ciągów +, ale nic zbyt ekscytującego.Haskell,
276 266 250 237 225 222217 bajtówStaje się coraz krótszy ... i coraz bardziej zaciemniony.
Oceń
n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)]
pierwszy przypadek testowy. Myślę, że zbliżam się do granic grania w golfa w tym algorytmie na Haskell.Ta funkcja jest tak wolna (co najmniej O (n 3 ), gdzie n jest całkowitym obwodem wszystkich prostokątów na wejściu), że nie mogę jej ocenić w dwóch ostatnich przypadkach testowych. Kiedy skompilowałem go z włączonymi optymalizacjami i uruchomiłem na 400-krotnej zmniejszonej wersji
[(0,249,250,0),(2,1,357,714)]
ostatniego testu, zakończyłem go w nieco ponad 12 sekund. Na tej podstawie rzeczywisty przypadek testowy zakończyłby się za około 25 lat.Wyjaśnienie (częściowe, rozwinę to, gdy będę miał czas)
Najpierw tworzymy dwie listy
h
iv
w następujący sposób. Dla każdego prostokąta na wejściu dzielimy jego granicę na segmenty o długości 1. Zachodnie punkty końcowe segmentów poziomych są przechowywane wh
, a południowe punkty końcowe segmentów pionowychv
jako listy[x,y]
długości 2. Współrzędnev
są przechowywane w odwróconym forma jak[y,x]
z powodów golfowych. Następnie po prostu zapętlamy obie listy i szukamy poziomej krawędzi[x,j]
i pionowej krawędzi[i,y]
tak, że (x < i
ii-x == j-y
są to północno-zachodnie i południowo-wschodnie narożniki kwadratu), i sprawdzamy, czy granice kwadratu znajdują się na prawidłowych listachh
iv
, podczas gdy wnętrze współrzędne nie są. Liczba pozytywnych wystąpień wyszukiwania jest wynikiem.źródło