Bayangkan sekelompok persegi panjang yang ditarik di pesawat, masing-masing persegi panjang dengan simpulnya pada koordinat bilangan bulat dan sisi-sisinya sejajar dengan sumbu:

Persegi panjang mempartisi pesawat menjadi beberapa daerah terpisah, berwarna merah dan biru di bawah ini:

Tujuan Anda adalah untuk menemukan jumlah daerah seperti itu yang kotak sempurna. Dalam contoh di atas, ada tiga:

Perhatikan bahwa alun-alun besar di tengah tidak dihitung karena itu bukan satu wilayah, tetapi terdiri dari beberapa daerah terpisah yang lebih kecil.

Memasukkan

Anda dapat menulis fungsi atau program lengkap untuk tantangan ini.

Input akan berupa 4nbilangan bulat non - negatif yang mendefinisikan npersegi panjang di pesawat. Setiap persegi panjang diwakili oleh dua simpul yang berlawanan, misalnya 4 9 7 8mewakili persegi panjang dengan simpul yang berlawanan (4, 9)dan (7, 8). Perhatikan bahwa persegi panjang ini juga bisa direpresentasikan sebagai 7 8 4 9atau 4 8 7 9.

Format input persisnya fleksibel (mis. String yang dipisahkan spasi, string yang dipisahkan koma, array bilangan bulat tunggal, daftar tupel koordinat, dan sebagainya) tetapi harap masuk akal dan berikan contoh cara menjalankan kode Anda di pos Anda. Anda tidak boleh memesan ulang input.

Untuk kesederhanaan, Anda dapat mengasumsikan bahwa tidak ada dua tepi yang akan tumpang tindih - ini termasuk tumpang tindih pada suatu titik. Secara khusus, ini menyiratkan bahwa tidak ada dua persegi panjang akan menyentuh ujung ke ujung atau ujung ke ujung, dan persegi panjang akan memiliki area bukan nol.

Keluaran

Program Anda harus mencetak atau mengembalikan satu bilangan bulat, yang merupakan jumlah wilayah kuadrat.

Mencetak gol

Ini adalah kode golf, jadi kode dalam byte paling sedikit menang.

Uji kasus

Memasukkan:

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

Keluaran:

4

Ini hanya empat kotak terpisah:

Memasukkan:

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

Keluaran:

3

Ini adalah contoh uji kasus di awal posting.

Memasukkan:

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

Keluaran:

7

Memasukkan:

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

Keluaran:

14

Memasukkan:

0 99999 100000 0

Keluaran:

0

Ini hanya satu persegi panjang besar.

Memasukkan:

0 99999 100000 0
2 1 142857 285714

Keluaran:

1

Dua persegi panjang besar yang tumpang tindih.

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

Ini adalah permintaan untuk ekstensi PostGIS ke PostgreSQL. Saya belum menghitung nilai input dalam 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

Penjelasan

Kueri membuat geometri untuk setiap pasangan koordinat. Serikat penyatuan berdering untuk benar simpul garis. Ubah hasilnya menjadi poligon dan uji lebar terhadap tinggi dan luasnya dua kali lipat terhadap jumlah setiap sisi kuadrat.

Ini akan berjalan sebagai permintaan mandiri pada setiap database PostgreSQL dengan Ekstensi PostGIS.

Sunting Ditemukan pasangan lagi.

Python 2, 480 436 386 352 byte

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

Mengambil daftar pasangan koordinat melalui STDIN dalam format:

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

dan mencetak hasilnya ke STDOUT.

Program yang sebenarnya, setelah penggantian string, adalah:

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)

Penjelasan

Alih-alih mengutak-atik poligon kompleks, program ini berurusan dengan segmen garis sederhana. Untuk setiap persegi panjang input, kami menambahkan masing-masing dari empat tepi ke daftar segmen kolektif, secara individual. Menambahkan segmen ke daftar berjalan sebagai berikut: kami menguji setiap segmen yang ada untuk persimpangan dengan segmen baru; jika kami menemukan persimpangan, kami membagi kedua segmen pada titik persimpangan dan melanjutkan. Untuk mempermudah, kami sebenarnya menyimpan dua daftar segmen yang terpisah: satu horizonal dan satu vertikal. Karena segmen tidak tumpang tindih, segmen horizontal hanya dapat memotong segmen vertikal dan sebaliknya. Lebih baik lagi, itu berarti bahwa semua persimpangan (tidak mempertimbangkan tepi dari persegi panjang yang sama) adalah "tepat," yaitu, kita tidak memiliki persimpangan berbentuk T, jadi "kedua sisi" dari setiap segmen benar-benar dibagi.

Setelah kami membuat daftar segmen, kami mulai menghitung kotak. Untuk setiap kombinasi dari empat segmen (khususnya, dua segmen horisontal dan dua yang vertikal,) kami menguji apakah mereka membentuk kuadrat. Selain itu, kami memverifikasi bahwa tidak ada simpul yang terletak di dalam kotak ini (yang dapat terjadi jika, misalnya, kami memiliki kotak kecil di dalam kotak yang lebih besar.) Ini memberi kami jumlah yang diinginkan. Perhatikan bahwa meskipun program menguji setiap kombinasi empat kali dalam urutan berbeda, urutan khusus dari koordinat segmen menjamin bahwa kami menghitung setiap kotak hanya sekali.

Haskell, 276 266 250 237 225 222 217 217 byte

Itu terus menjadi lebih pendek ... dan lebih dikaburkan.

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

Evaluasi n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)]kasus uji pertama. Saya pikir saya semakin mendekati batas golf algoritma ini di Haskell.

Fungsi ini sangat lambat (setidaknya O (n ³ ) di mana n adalah perimeter total dari semua persegi panjang dalam input) sehingga saya tidak dapat mengevaluasinya pada dua kasus uji terakhir. Ketika saya mengompilasinya dengan optimisasi dihidupkan dan menjalankannya pada versi menyusut 400 kali [(0,249,250,0),(2,1,357,714)]dari tes terakhir, selesai dalam waktu lebih dari 12 detik. Berdasarkan ini, test case yang sebenarnya akan selesai dalam waktu sekitar 25 tahun.

Penjelasan (sebagian, saya akan memperluas ini ketika saya punya waktu)

Kami pertama membangun dua daftar hdan vsebagai berikut. Untuk setiap persegi panjang dalam input, kami membagi perbatasannya menjadi segmen dengan panjang 1. Titik akhir barat segmen horizontal disimpan h, dan titik akhir selatan segmen vertikal v, sebagai daftar [x,y]panjang 2. Koordinat vdisimpan dalam terbalik formulir [y,x]untuk alasan golf. Kemudian kita hanya mengulang kedua daftar dan mencari tepi horizontal [x,j]dan tepi vertikal [i,y]sehingga x < idan i-x == j-y(jadi mereka adalah sudut barat laut dan tenggara dari sebuah kotak), dan memeriksa bahwa batas-batas kotak berada di daftar yang benar hdan v, sementara bagian dalam koordinat tidak. Jumlah contoh positif dari pencarian adalah output.