Imagine um monte de retângulos desenhados no plano, cada retângulo com seus vértices em coordenadas inteiras e seus lados paralelos aos eixos:

Os retângulos dividem o avião em várias regiões separadas, coloridas em vermelho e azul abaixo:

Seu objetivo é encontrar o número dessas regiões que são quadrados perfeitos. No exemplo acima, existem três:

Observe que o grande quadrado no meio não é contado, pois não é uma região única, mas é composto de várias regiões disjuntas menores.

Entrada

Você pode escrever uma função ou um programa completo para esse desafio.

A entrada será 4nnúmeros inteiros não negativos que definem nretângulos no plano. Cada retângulo é representado por dois vértices opostos, por exemplo, 4 9 7 8representa o retângulo com vértices opostos (4, 9)e (7, 8). Observe que esse retângulo também pode ser representado como 7 8 4 9ou 4 8 7 9.

O formato exato de entrada é flexível (por exemplo, sequência separada por espaço, sequência separada por vírgula, matriz única de números inteiros, lista de tuplas de coordenadas etc.), mas seja razoável e dê um exemplo de como executar seu código em sua postagem. Você não pode reordenar a entrada.

Para simplificar, você pode assumir que não há duas arestas sobrepostas - isso inclui a sobreposição em um vértice. Em particular, isso implica que dois retângulos tocarão de ponta a ponta ou canto a canto, e os retângulos terão área diferente de zero.

Saída

Seu programa deve imprimir ou retornar um único número inteiro, que é o número de regiões quadradas.

Pontuação

Este é o código golf, portanto o código com o menor número de bytes vence.

Casos de teste

Entrada:

0 0 5 5
6 8 10 4
14 16 11 13
19 1 18 2

Saída:

4

São simplesmente quatro quadrados disjuntos:

Entrada:

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

Saída:

3

Este é o caso de teste de exemplo no início da postagem.

Entrada:

0 9 15 12
6 3 18 15
9 6 12 20
13 4 17 8

Saída:

7

Entrada:

5 9 11 10
5 12 11 13
6 8 7 14
9 8 10 14
13 8 14 9
13 10 14 14

Saída:

14

Entrada:

0 99999 100000 0

Saída:

0

Este é apenas um grande retângulo.

Entrada:

0 99999 100000 0
2 1 142857 285714

Saída:

1

Dois retângulos grandes que se sobrepõem.

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

Esta é uma consulta para a extensão PostGIS no PostgreSQL. Não contei os valores de entrada no total.

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

Explicação

A consulta cria geometrias para cada par de coordenadas. Une os anéis externos para dar um nó adequado às linhas. Transforma os resultados em polígonos e testa a largura em relação à altura e a área dobrada em relação à soma de cada lado ao quadrado.

Ele será executado como uma consulta independente em qualquer banco de dados PostgreSQL com a extensão PostGIS.

Editar Encontrei mais alguns.

Python 2, 480 436 386 352 bytes

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 "})

Leva uma lista de pares de coordenadas através de STDIN no formato:

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

e imprime o resultado em STDOUT.

O programa real, após a substituição da string, é:

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)

Explicação

Em vez de mexer com polígonos complexos, este programa lida com segmentos de linha simples. Para cada retângulo de entrada, adicionamos cada uma de suas quatro arestas a uma lista de segmentos coletiva, individualmente. A adição de um segmento à lista é a seguinte: testamos cada um dos segmentos existentes quanto à interseção com o novo segmento; se encontrarmos um cruzamento, dividimos os dois segmentos no ponto de cruzamento e continuamos. Para facilitar, mantemos duas listas de segmentos separadas: uma horizontal e outra vertical. Como os segmentos não se sobrepõem, os segmentos horizontais só podem cruzar segmentos verticais e vice-versa. Melhor ainda, significa que todas as interseções (sem considerar as arestas do mesmo retângulo) são "apropriadas", ou seja, não temos interseções em forma de T, portanto "os dois lados" de cada segmento são verdadeiramente divididos.

Depois que construímos a (s) lista (s) de segmentos, começamos a contar os quadrados. Para cada combinação de quatro segmentos (principalmente dois horizontais e dois verticais), testamos se eles formam um quadrado. Além disso, verificamos que nenhum vértice está dentro desse quadrado (o que pode acontecer se, por exemplo, tivermos um quadrado pequeno dentro de um quadrado maior). Isso nos dá a quantidade desejada. Observe que, embora o programa teste cada combinação quatro vezes em ordens diferentes, a ordem específica das coordenadas do segmento garante que contemos cada quadrado apenas uma vez.

Haskell, 276266 250237252222 217 bytes

Ele fica cada vez mais curto ... e mais ofuscado.

(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]])[[],[]]

Avalie n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)]para o primeiro caso de teste. Acho que estou chegando perto dos limites do golfe desse algoritmo em Haskell.

Essa função é tão lenta (pelo menos O (n ³ ) onde n é o perímetro total de todos os retângulos na entrada) que não posso avaliá-la nos dois últimos casos de teste. Quando o compilei com otimizações ativadas e o executei na versão encolhida 400 vezes [(0,249,250,0),(2,1,357,714)]do último teste, ele terminou em pouco mais de 12 segundos. Com base nisso, o caso de teste real terminaria em cerca de 25 anos.

Explicação (parcial, expandirei isso quando tiver tempo)

Primeiro criamos duas listas he da vseguinte maneira. Para cada retângulo na entrada, dividimos sua borda em segmentos de comprimento 1. Os pontos de extremidade oeste dos segmentos horizontais são armazenados he os pontos ao sul dos segmentos verticais v, como listas [x,y]de comprimento 2. As coordenadas vsão armazenadas de forma invertida. forma [y,x]por razões de golfe. Em seguida, passamos pelas duas listas e pesquisamos a borda horizontal [x,j]e a vertical de [i,y]modo que x < ie i-x == j-y(para que sejam os cantos noroeste e sudeste de um quadrado) e verificamos se as bordas do quadrado estão nas listas corretas he v, enquanto o interior coordenadas não são. O número de instâncias positivas da pesquisa é a saída.