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ą 4nnieujemnymi liczbami całkowitymi definiującymi nprostokąty w płaszczyźnie. Każdy prostokąt jest reprezentowany przez dwa przeciwstawne wierzchołki, np. 4 9 7 8Reprezentuje 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 9lub 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.

SQL (POSTGIS), 286 269 261 240 226 218 216

To jest zapytanie o rozszerzenie PostGIS do PostgreSQL. Nie policzyłem wartości wejściowych w sumie.

SELECT SUM(1)FROM(SELECT(ST_Dump(ST_Polygonize(g))).geom d FROM(SELECT ST_Union(ST_Boundary(ST_MakeEnvelope(a,b,c,d)))g FROM(VALUES
-- Coordinate input
(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)
)i(a,b,c,d))i)a WHERE(ST_XMax(d)-ST_XMin(d))^2+(ST_YMax(d)-ST_YMin(d))^2=ST_Area(d)*2

Wyjaśnienie

Zapytanie tworzy geometrie dla każdej pary współrzędnych. Łączy zewnętrzne pierścienie, aby prawidłowo węzły linii. Przekształca wyniki w wielokąty i sprawdza szerokość względem wysokości, a obszar podwaja się w stosunku do sumy każdej strony do kwadratu.

Będzie działał jako samodzielne zapytanie w dowolnej bazie danych PostgreSQL z rozszerzeniem PostGIS.

Edytuj Znaleziono jeszcze kilka.

Python 2, 480 436 386 352 bajty

exec u"""s=sorted;H=[];V=[]
FRIinput():
 S=2*map(s,zip(*R))
 FiI0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    FeIs(H):
     C,(A,B)=e
     if a<C<b&A<c<B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D)&c==C==(b,B)&B-b==D-d&1-any(d<X[0]<D&b<y<B Fy,XIH)Fb,aIH FB,AIH Fd,cIV FD,CIV)""".translate({70:u"for ",73:u" in ",38:u" and "})

Pobiera listę par współrzędnych przez STDIN w formacie:

[  [(x, y), (x, y)],  [(x, y), (x, y)],  ...  ]

i drukuje wynik do STDOUT.

Rzeczywistym programem, po zamianie łańcucha, jest:

s=sorted;H=[];V=[]
for R in input():
 S=2*map(s,zip(*R))
 for i in 0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    for e in s(H):
     C,(A,B)=e
     if a<C<b and A<c<B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D) and c==C==(b,B) and B-b==D-d and 1-any(d<X[0]<D and b<y<B for y,X in H)for b,a in H for B,A in H for d,c in V for D,C in V)

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.

Haskell, 276 266 250 237 225 222 217 bajtów

Staje się coraz krótszy ... i coraz bardziej zaciemniony.

(x#i)l=mapM id[[min x i..max x i-1],l]
(y!j)l f=and[p l==p(f[y,j])|p<-map elem$f[y..j]]
s[h,v]=sum[1|[x,j]<-h,[y,i]<-v,x<i,i-x==j-y,(y!j)h$x#i,(x!i)v$y#j]
n=s.foldr(\(x,y,i,j)->zipWith(++)[x#i$[y,j],y#j$[x,i]])[[],[]]

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 ³ ), 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 hi vw 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 w h, a południowe punkty końcowe segmentów pionowych vjako listy [x,y]długości 2. Współrzędne vsą 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 < ii i-x == j-ysą to północno-zachodnie i południowo-wschodnie narożniki kwadratu), i sprawdzamy, czy granice kwadratu znajdują się na prawidłowych listach hi v, podczas gdy wnętrze współrzędne nie są. Liczba pozytywnych wystąpień wyszukiwania jest wynikiem.