Anda diberi array / daftar / vektor pasangan bilangan bulat yang mewakili koordinat kartesius poin pada bidang Euclidean 2D; semua koordinat antara dan , duplikat diperbolehkan. Temukan area lambung cembung titik-titik itu, dibulatkan ke bilangan bulat terdekat; titik tengah yang tepat harus dibulatkan ke bilangan bulat genap terdekat. Anda dapat menggunakan angka floating-point dalam perhitungan menengah, tetapi hanya jika Anda dapat menjamin bahwa hasil akhir akan selalu benar. Ini adalah kode-golf , sehingga program terpendek yang benar menang.
The convex hull dari satu set poin adalah himpunan cembung terkecil yang berisi . Pada bidang Euclidean, untuk setiap titik tunggal , itu adalah titik itu sendiri; untuk dua titik berbeda, itu adalah garis yang mengandung mereka, untuk tiga titik non-collinear, itu adalah segitiga yang terbentuk, dan sebagainya.
Penjelasan visual yang bagus tentang cangkang cembung, digambarkan sebagai membayangkan semua titik sebagai paku di papan kayu, dan kemudian merentangkan karet gelang di sekelilingnya untuk melampirkan semua poin:
Beberapa test case:
Input: [[50, -13]]
Result: 0
Input: [[-25, -26], [34, -27]]
Result: 0
Input: [[-6, -14], [-48, -45], [21, 25]]
Result: 400
Input: [[4, 30], [5, 37], [-18, 49], [-9, -2]]
Result: 562
Input: [[0, 16], [24, 18], [-43, 36], [39, -29], [3, -38]]
Result: 2978
Input: [[19, -19], [15, 5], [-16, -41], [6, -25], [-42, 1], [12, 19]]
Result: 2118
Input: [[-23, 13], [-13, 13], [-6, -7], [22, 41], [-26, 50], [12, -12], [-23, -7]]
Result: 2307
Input: [[31, -19], [-41, -41], [25, 34], [29, -1], [42, -42], [-34, 32], [19, 33], [40, 39]]
Result: 6037
Input: [[47, 1], [-22, 24], [36, 38], [-17, 4], [41, -3], [-13, 15], [-36, -40], [-13, 35], [-25, 22]]
Result: 3908
Input: [[29, -19], [18, 9], [30, -46], [15, 20], [24, -4], [5, 19], [-44, 4], [-20, -8], [-16, 34], [17, -36]]
Result: 2905
[[0, 0], [1, 1], [0, 1]]
benar-benar harus menghasilkan daripada . 0Jawaban:
SQL Server 2012+, 84 byte
Memanfaatkan fungsi geometri dan agregat dalam SQL Server. Coordindate berasal dari tabel
A
dengan kolomx
dany
.sumber
Java 10,
405... tidak cocok lagi; lihat edit histori ..317316 bytes-52 byte terima kasih kepada @ OlivierGrégoire
-3 byte terima kasih kepada @PeterTaylor
-7 byte terima kasih kepada @ceilingcat
Cobalah online.
Atau 299 byte tanpa pembulatan .. .
Penjelasan:
Ada tiga langkah yang harus dilakukan:
Untuk menghitung koordinat yang merupakan bagian dari Convex Hull, kami menggunakan pendekatan berikut:
Adapun kode:
sumber
Bahasa Wolfram (Mathematica) , 27 byte
Cobalah online!
sumber
JavaScript (ES6),
191189 byteMenerapkan gerakan Jarvis (alias algoritma pembungkusan hadiah).
Cobalah online!
Atau 170 byte tanpa skema pembulatan yang rumit.
sumber
R ,
858178 byteCobalah online!
Mengambil input sebagai matriks 2 kolom - pertama untuk
x
, kedua untuky
. R'sround
sebenarnya menggunakan metode pembulatan bankir, jadi kami cukup beruntung di sini.Terima kasih kepada Giuseppe untuk -3 byte.
sumber
[Paket R + sp], 55 byte
Cobalah di RDRR
Fungsi yang mengambil matriks anx 2 dan mengembalikan area yang dibulatkan. Ini menggunakan
sp
paket. Thedrop=F
diperlukan untuk menangani kasus satu koordinasi. RDRR digunakan untuk demo karena TIO tidak memilikisp
paket.sumber