Masalah happy ending (sebenarnya sebuah teorema) menyatakan hal itu
Setiap set lima titik di pesawat dalam posisi umum memiliki subset dari empat titik yang membentuk simpul dari segiempat cembung.
Masalahnya dinamai oleh Paul Erd ketika dua ahli matematika yang pertama kali menangani masalah tersebut, Ester Klein dan George Szekeres, bertunangan dan kemudian menikah.
Klarifikasi:
- Posisi umum di sini berarti bahwa tidak ada tiga titik yang collinear.
Segi empat yang dibentuk oleh empat simpul akan selalu dianggap non-berpotongan, terlepas dari urutan poin. Sebagai contoh, mengingat empat poin
[1 1]
,[1 2]
,[2 1]
,[2 2]
yang segiempat dimaksudkan adalah persegi, bukan kupu-kupu:Quadrilateral non-berpotongan adalah cembung jika tidak ada sudut interior melebihi 180 derajat; atau setara jika kedua diagonal terletak di dalam segiempat.
Tantangan
Diberikan 5 poin dengan koordinat bilangan bulat positif, menghasilkan 4 poin yang membentuk segiempat cembung.
Aturan
Jika ada beberapa solusi (yaitu, beberapa set 4 poin), Anda dapat secara konsisten memilih untuk mengeluarkan salah satu dari mereka atau semua.
Format input dan output fleksibel seperti biasa (array, daftar, daftar daftar, string dengan pemisah yang masuk akal, dll).
Golf kode, byte paling sedikit menang.
Uji kasus
Memasukkan:
[6 8] [1 10] [6 6] [5 9] [8 10]
Hanya ada satu kemungkinan output:
[6 8] [1 10] [6 6] [5 9]
Memasukkan:
[3 8] [7 5] [6 9] [7 8] [5 1]
Ada lima solusi:
[3 8] [7 5] [6 9] [7 8] [3 8] [7 5] [6 9] [5 1] [3 8] [7 5] [7 8] [5 1] [3 8] [6 9] [7 8] [5 1] [7 5] [6 9] [7 8] [5 1]
Memasukkan:
[4 8] [1 9] [9 9] [10 2] [1 6]
Ada tiga solusi:
[4 8] [1 9] [10 2] [1 6] [4 8] [9 9] [10 2] [1 6] [1 9] [9 9] [10 2] [1 6]
Sebagai ilustrasi, berikut adalah tiga solusi untuk kasus ini:
Jawaban:
CJam,
373432 byteTidak yakin apakah
:-V
cukup senang, tetapi seperti yang ditunjukkan K Zhang, ada=}
akhirnya. :)Ini hanya mencetak satu solusi karena menghapus duplikat akan lebih mahal.
Uji di sini.
Penjelasan
Idenya cukup sederhana. Kami menghasilkan semua segiempat yang mungkin (termasuk semua pemesanan poin) dan kemudian pilih yang cembung. Kami menguji kecemburuan dengan melihat setiap pasang tepi dan memeriksa bahwa mereka semua berbalik ke arah yang sama.
Perasaan balik dapat diperoleh dengan mudah dari produk titik. Jika Anda mengambil tiga titik berurutan pada segi empat, dan menggambar garis dari yang pertama ke yang kedua, dan yang pertama ke yang ketiga, dan kemudian memproyeksikan yang terakhir ke tegak lurus dari yang pertama ... Anda mendapatkan nomor yang tanda memberitahu Anda apakah tiga poin ini belok kiri atau kanan. (Saya mungkin harus menambahkan diagram untuk ini.) Ini "memproyeksikan ke tegak lurus" adalah suara yang cukup terlibat, tetapi benar-benar hanya berarti bahwa kita membalikkan salah satu dari dua vektor dan mengurangi komponen setelah penggandaan daripada menambahkannya. Jadi, inilah kodenya ...
sumber
!}
dapat dianggap sebagai mengedipkan mata jugaMATLAB, 67 byte
Input dalam bentuk matriks 2D di mana kolomnya masing-masing X dan Y:
Semua set 4 poin yang membuat segiempat cembung ditampilkan dalam format yang sama.
Berikut ini adalah demo yang sedikit dimodifikasi untuk bekerja dengan Oktaf
Penjelasan
Solusi ini mengambil semua himpunan bagian dari 4 poin input (urutan tidak masalah). Untuk melakukan ini, kita membuat matriks identitas dan meniadakan itu:
~eye(5)
. Kami loop melalui kolom matriks ini dank
(indeks loop) adalah array logis yang menentukan mana dari 4 poin untuk dipertimbangkan. Kami kemudian menggunakan ini untuk mengambil 4 poin XY ini dari input (I(k,:)
).Kami kemudian menghitung lambung cembung dari 4 poin ini (
convhull
). Output dariconvhull
adalah indeks input yang sesuai dengan poin yang membentuk lambung cembung (dengan indeks pertama digandakan untuk menutup lambung).Untuk segiempat cembung, keempat poin akan menjadi bagian dari lambung cembung dari poin yang sama (
nnz(convhull(points)) > 4
). Jika kami mendeteksi bahwa ini adalah masalahnya, kami menampilkan poin yang digunakan untuk iterasi khusus ini.sumber
Javascript (ES6),
306293283 bytePenjelasan :
Fungsi
c
menghitung produk silang dari vektor antara 3 titik yang berdekatan dari poligon dan mengembalikan 1 jika positif dan 0 sebaliknya (catatan: produk silang tidak boleh nol karena poin tidak bisa menjadi co-linear).Fungsi
k
danj
menghasilkan semua permutasi siklik (mengabaikan membalik urutan) dari array input.Fungsi 'i' kemudian dipanggil untuk setiap permutasi siklik untuk menghitung jumlah fungsi
c
untuk masing-masing 4 kembar tiga koordinat yang berdekatan. Jika semua produk silang memiliki tanda yang sama maka mereka semua akan menjadi 0 atau 1 dan total menjadi 0 (modulo 4) dan poligon cekung dan didorong ke dalam array output. Jika ada triplet yang memiliki tanda berbeda maka totalnya akan menjadi nol (modulo 4) dan poligonnya cembung.Fungsi
f
ini digunakan untuk menginisialisasi array output dan kemudian memanggil fungsi-fungsi di atas sebelum mengembalikan output.Tes :
Edit :
Dapat juga menangani poin co-linear menggunakan versi asli dan mengubah dua baris pertama menjadi:
Namun, karena case tersebut secara khusus dikecualikan dalam pertanyaan maka karakter tambahan tidak diperlukan.
sumber
Mathematica
10596 byteSelect[#~Subsets~{4},f@#&]&
memilih, dari daftar (5) poin, himpunan bagian dari 4 poin yang memuaskanf
.f
puas ketika masing-masing titik, dari 4 poin di set, kebohongan padaRegionBoundary
satuConvexHull
dari 4 poin.Uji Kasus
1. Mari kita lihat 5 cangkang subset cembung (masing-masing 4 poin) dari {{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}} .
{{{6, 8}, {1, 10}, {6, 6}, {5, 9}}}}
{{6, 8}, {1, 10}, {6, 6}, {5, 9}} adalah satu-satunya solusi; masing-masing dari empat titik berfungsi sebagai simpul dari cembung cembung (dari 4 poin yang sama).
{{6, 8}, {1, 10}, {6, 6}, {8, 10}} bukan solusi; convex hull hanya memiliki 3 simpul. {6, 8} terletak di dalam lambung.
Himpunan bagian yang tersisa juga bukan solusi:
2. {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} memiliki tiga solusi.
{
{{4, 8}, {1, 9}, {10, 2}, {1, 6}},
{{4, 8}, {9, 9}, {10, 2}, {1, 6 }},
{{1, 9}, {9, 9}, {10, 2}, {1, 6}}
}
3. {{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}} memiliki 5 solusi.
{
{{3, 8}, {7, 5}, {6, 9}, {7, 8}},
{{3, 8}, {7, 5}, {6, 9}, {5, 1 }},
{{3, 8}, {7, 5}, {7, 8}, {5, 1}},
{{3, 8}, {6, 9}, {7, 8}, {5 , 1}},
{{7, 5}, {6, 9}, {7, 8}, {5, 1}}
}
Perhatikan bahwa masing-masing dari lima titik terletak pada batas cembung semua titik.
Jika salah satu poin dihilangkan, 4 poin yang tersisa masing-masing akan menjadi simpul dari lambung cembung yang dikurangi.
sumber