Dalam tantangan ini, Anda diberi dua persegi panjang yang tumpang tindih, dan Anda perlu menghitung persegi panjang yang dibuat dengan menghapus satu dari yang lain.
Misalnya, jika Anda menghapus persegi panjang merah dari yang hitam:
Anda berakhir dengan salah satu dari dua set persegi panjang berikut:
Anda juga harus menangani hal-hal berikut:
Untuk lebih eksplisit:
- Anda akan memasukkan koordinat dua persegi panjang, A dan B.
- Anda perlu menampilkan persegi panjang non-tumpang tindih paling sedikit yang mencakup semua area A tanpa B. Penutup yang memungkinkan diizinkan
- Koordinat persegi panjang dilewatkan sebagai 4 bilangan bulat. Anda dapat mengirimkannya dalam dua pasangan (mewakili dua titik sudut), atau sebagai tuple / daftar 4 bilangan bulat. Input dan output Anda harus konsisten.
- A dan B belum tentu tumpang tindih atau menyentuh, dan masing-masing akan memiliki area minimal 1
Kasus uji:
[(0 0) (5 5)] [(3 4) (8 7)] -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)] -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)] #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)] -> #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)] -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)] #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)] -> [(1 5) (7 8)] #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)] -> [(4 1) (10 5)] [(4 7) (10 9)] #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)] -> [(1 1) (8 6)] #Only possible output
Ini adalah kode-golf , jadi buat kode Anda sesingkat mungkin!
code-golf
geometry
grid
set-partitions
Nathan Merrill
sumber
sumber
{(x1, y1), (x2, y2)}
berlakux1 < x2
dany1 < y2
?Jawaban:
Python 2 ,
375360345343 byteCobalah online!
EDIT: -15 dari saran dari @notjagan; lain -15 dengan pengkodean ulang array solusi persegi panjang ke format int36 dan tabel pencarian pendek; lain -2 dengan mengganti produk dengan p sesuai @musicman.
Fungsi yang mengambil dua persegi panjang, masing-masing persegi menjadi tupel ((kiri, atas), (kanan, bawah)); mengembalikan daftar persegi panjang yang dihasilkan.
Strategi dasar:
Dalam diagram di atas, masing-masing titik A dan B adalah kiri atas dan kanan bawah, dari persegi panjang 'Sumber' (persegi pertama).
Kami menemukan penempatan masing-masing kiri atas
(u,v)
dan kanan bawah(x,y)
persegi panjang 'Topeng' di kotak itu.Jika kedua titik ini ada di kolom pertama atau terakhir; atau baris pertama atau terakhir; maka tidak ada tumpang tindih; dan kita bisa mengembalikan hanya Sumber rect.
Kalau tidak, ada 16 kasus yang tersisa; misalnya, contoh pertama OP adalah kasus yang dapat kita beri label
(1,1),(2,2)
. Setiap kasus dapat dipetakan ke seperangkat persegi panjang yang dihasilkan yang sudutnya selalu berkoordinasi dengan nilai horizontal di salah satu persegi panjang Sumber kiri, kanan, atau persegi panjang Mask kiri, kanan; dan juga untuk nilai-nilai vertikal, bagian atas, bawah, atau topeng Sumber.Sebagai contoh, untuk
(1,1),(2,2)
kasus ini, persegi panjang akan((l,t),(T,r))
dan((l,T),(R,b))
, di manal,t,r,b
danL,T,R,B
adalah kiri, atas, kanan dan bawah dari persegi panjang Sumber dan Mask, masing-masing.Jadi kita dapat membuat tabel pencarian yang memetakan koordinat ke himpunan semua kombinasi yang mungkin (yaitu tentang apa
product(product(*zip(*)))
bit itu) ke himpunan persegi panjang yang harus disediakan untuk masing-masing kasus (yang, setelah beberapa dekompresi golf) , adalah isi dari daftar sisanya adalah tentang).sumber
p=product
dan menggantiproduct(product
denganp(p
JavaScript, 115 byte
versi yang tumpang tindih:
Masukan dalam format berikut:
f([1,1,8,8])([0,6,9,9])
Nyatakan input sebagai ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))
Jika salah satu dari kondisi berikut ini terpenuhi, kembalikan persegi panjang pertama seperti:
jika tidak
sumber
f([0, 30, 10, 40])([5, 1, 6, 2])
harus kembali[[0, 30, 10, 40]]
tetapi sebaliknya kembali[[0,30,5,40],[6,30,10,40]]
Java, 268 byte
Tidak disatukan
Masukan input sebagai argumen. Contoh
sumber
Python 2 , 272 byte
Cobalah online!
Ini bekerja dengan menguji setiap sel di dalam persegi panjang pertama untuk kiri = 1, aboveness = 4, rightness = 2, dan belowness = 8 w / r ke yang lain, dan ORing hasilnya. Jika yang lain tidak berpotongan = 0 dengan yang pertama, maka yang asli dikembalikan, jika tidak, kombinasi dari irisan kiri, irisan kanan, irisan atas dan irisan bawah dikembalikan, dengan akomodasi untuk tumpang tindih.
sumber