Imaginez un tas de rectangles dessinés dans le plan, chaque rectangle avec ses sommets en coordonnées entières et ses côtés parallèles aux axes:

Les rectangles divisent l'avion en un certain nombre de régions disjointes, colorées en rouge et bleu ci-dessous:

Votre objectif est de trouver le nombre de ces régions qui sont des carrés parfaits. Dans l'exemple ci-dessus, il y en a trois:

Notez que le grand carré au milieu n'est pas compté car il ne s'agit pas d'une seule région, mais plutôt de plusieurs petites régions disjointes.

Contribution

Vous pouvez écrire une fonction ou un programme complet pour ce défi.

L'entrée sera 4ndes entiers non négatifs définissant des nrectangles dans le plan. Chaque rectangle est représenté par deux sommets opposés, par exemple 4 9 7 8représente le rectangle avec des sommets opposés (4, 9)et (7, 8). Notez que ce rectangle peut également être représenté par 7 8 4 9ou 4 8 7 9.

Le format d'entrée exact est flexible (par exemple une chaîne séparée par des espaces, une chaîne séparée par des virgules, un seul tableau d'entiers, une liste de tuples de coordonnées, etc.), mais soyez raisonnable et donnez un exemple de la façon d'exécuter votre code dans votre message. Vous ne pouvez pas réorganiser l'entrée.

Pour simplifier, vous pouvez supposer qu'il n'y aura pas deux arêtes qui se chevaucheront - cela inclut le chevauchement au sommet. En particulier, cela implique qu'aucun deux rectangles ne toucheront bord à bord ou coin à coin, et que les rectangles auront une zone non nulle.

Sortie

Votre programme doit imprimer ou renvoyer un seul entier, qui est le nombre de régions carrées.

Notation

C'est le code golf, donc le code dans le moins d'octets gagne.

Cas de test

Contribution:

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

Sortie:

4

Il s'agit simplement de quatre carrés disjoints:

Contribution:

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

Sortie:

3

Ceci est l'exemple de cas de test au début de la publication.

Contribution:

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

Sortie:

7

Contribution:

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

Sortie:

14

Contribution:

0 99999 100000 0

Sortie:

0

Ce n'est qu'un grand rectangle.

Contribution:

0 99999 100000 0
2 1 142857 285714

Sortie:

1

Deux grands rectangles qui se chevauchent.

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

Il s'agit d'une requête pour l'extension PostGIS à PostgreSQL. Je n'ai pas compté les valeurs d'entrée dans le 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

Explication

La requête crée des géométries pour chaque paire de coordonnées. Rassemble les anneaux extérieurs pour assembler correctement les lignes. Transforme les résultats en polygones et teste la largeur par rapport à la hauteur et la surface a doublé par rapport à la somme de chaque côté au carré.

Il s'exécutera en tant que requête autonome sur n'importe quelle base de données PostgreSQL avec l'extension PostGIS.

Modifier J'ai trouvé un couple de plus.

Python 2, 480 436 386 352 octets

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

Prend une liste de paires de coordonnées via STDIN au format:

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

et imprime le résultat dans STDOUT.

Le programme réel, après remplacement de la chaîne, est le suivant:

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)

Explication

Au lieu de jouer avec des polygones complexes, ce programme traite de segments de ligne simples. Pour chaque rectangle d'entrée, nous ajoutons chacun de ses quatre bords à une liste de segments collectifs, individuellement. L'ajout d'un segment à la liste se déroule comme suit: nous testons chacun des segments existants pour l'intersection avec le nouveau segment; si nous trouvons une intersection, nous divisons les deux segments au point d'intersection et continuons. Pour faciliter les choses, nous gardons en fait deux listes de segments distinctes: une horizontale et une verticale. Étant donné que les segments ne se chevauchent pas, les segments horizontaux ne peuvent couper que les segments verticaux et vice versa. Mieux encore, cela signifie que toutes les intersections (sans tenir compte des bords du même rectangle) sont "correctes", c'est-à-dire que nous n'avons pas d'intersections en T, donc "les deux côtés" de chaque segment sont vraiment divisés.

Une fois que nous avons construit la ou les listes de segments, nous commençons à compter les carrés. Pour chaque combinaison de quatre segments (en particulier, deux segments horizontaux et deux verticaux), nous testons s'ils forment un carré. De plus, nous vérifions qu'aucun sommet ne se trouve à l'intérieur de ce carré (ce qui peut arriver si, par exemple, nous avons un petit carré à l'intérieur d'un plus grand). Cela nous donne la quantité souhaitée. Notez que même si le programme teste chaque combinaison quatre fois dans des ordres différents, l'ordre particulier des coordonnées du segment garantit que nous ne comptons chaque carré qu'une seule fois.

Haskell, 276 266 250 237 225 222 217 octets

Il devient de plus en plus court ... et plus obscurci.

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

Évaluez n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)]le premier cas de test. Je pense que je me rapproche des limites du golf cet algorithme sur Haskell.

Cette fonction est si lente (au moins O (n ³ ) où n est le périmètre total de tous les rectangles en entrée) que je ne peux pas l'évaluer sur les deux derniers cas de test. Lorsque je l'ai compilé avec des optimisations activées et exécuté sur la version 400 fois réduite [(0,249,250,0),(2,1,357,714)]du dernier test, il s'est terminé en un peu plus de 12 secondes. Sur cette base, le cas de test réel se terminerait dans environ 25 ans.

Explication (partielle, je développerai cela quand j'aurai le temps)

Nous construisons d'abord deux listes het vcomme suit. Pour chaque rectangle dans l'entrée, nous divisons sa bordure en segments de longueur 1. Les extrémités ouest des segments horizontaux sont stockées dans h, et les extrémités sud des segments verticaux dans v, sous forme de listes [x,y]de longueur 2. Les coordonnées dans vsont stockées dans un sens inversé forme comme [y,x]pour des raisons de golf. Ensuite, nous passons en boucle sur les deux listes et recherchons le bord horizontal [x,j]et le bord vertical [i,y]tels que x < iet i-x == j-y(donc ce sont les coins nord-ouest et sud-est d'un carré), et vérifions que les bordures du carré sont dans les listes correctes het v, tandis que l'intérieur les coordonnées ne le sont pas. Le nombre d'instances positives de la recherche est la sortie.