Tantangannya adalah, mengingat daftar poin, mengurutkan sedemikian rupa sehingga, ketika mereka terhubung dalam urutan ini, mereka tidak pernah berpotongan.
Format input (baca dari stdin):
X Y
1 2
3 4
5 6
...
Output harus sama dengan input, tetapi diurutkan.
Aturan:
- Anda bisa mulai dari titik mana pun.
- Poin terakhir harus sama dengan yang pertama, membuat sirkuit dekat.
- Itu harus dilakukan mengingat grid Cartesian.
- Anda dapat mengasumsikan bahwa titik input tidak semuanya terletak pada satu baris.
- Titik akhir setiap baris tidak dihitung sebagai berpotongan.
Untuk bantuan lebih lanjut:
Jawaban:
Mathematica -
2030 karakterHanya bagian penyortiran
Seluruh kode pengujian, yang terdiri dari menghasilkan 100 poin acak dan merencanakan garis
+26 karakter
Jika Anda meminta input / ouput yang tepat, maka
+2 karakter
Hanya menambahkan
N@
karena kode di atas hanya berfungsi pada bilangan real dan bukan pada bilangan bulat karena perilaku aneh Matematika ketika menyortir ekspresi simbolik
EDIT Saya baru menyadari jika poin tidak di sekitar titik asal tidak akan berfungsi, jadi itu juga membutuhkan pergeseran ke pusat poin
sumber
ArcTan
hasilnya sebenarnya sama hingga yang terakhir. Apakah Anda tahu mengapa demikian? (Inilah kasusnya jika Anda ingin bermain-main dengannya{{1, 2}, {2, 4}, {3, 6}, {-5, 5}, {-6, -12}, {5, -5}}
).SortBy
dokumentasi: Jika beberapa f [e_i] sama, maka urutan kanonik e_i yang sesuai digunakan.Pertanyaannya telah berubah, jadi jawaban ini berisi versi yang berbeda, dengan dan tanpa jalur tertutup.
Perl, jalur terbuka, 69 byte
Setiap titik diharapkan dalam STDIN sebagai garis, dengan koordinat dipisahkan oleh ruang putih.
Semua format angka didukung oleh Perl yang diinterpretasikan sebagai angka (termasuk angka floating point).
Contoh:
Keluaran:
Tidak Disatukan:
Varian sirkuit
Dalam versi pertanyaan pertama, ada koneksi antara titik terakhir dan pertama untuk membuat sirkuit.
Titik tengah tidak ada, 253 byte
Varian ini bisa gagal, jika pusat adalah salah satu poin, lihat contoh 3.
Suntingan:
Dalam jawabannya, swish menyadarinya, bahwa titik harus dipusatkan di sekitar titik asal untuk memastikan sirkuit bebas silang:
Perbaikan bug: kasus khusus untuk sumbu x negatif telah menyertakan sumbu x positif.
Contoh 1:
Output 1:
Contoh 2:
Menguji representasi angka dan transformasi koordinat.
Output 2:
Tidak Disatukan:
Tanpa batasan, 325 byte
Dalam versi sebelumnya, pusat diletakkan di awal dan titik-titik terakhir pada sumbu negatif diurutkan dalam urutan terbalik untuk mendapatkan cross-free ke pusat lagi. Namun, ini tidak cukup, karena poin terakhir bisa terletak pada garis yang berbeda. Jadi contoh 3 berikut akan gagal.
Ini diperbaiki dengan memindahkan titik pusat sedikit ke atas dan kanan. Karena keterpusatan, harus ada setidaknya satu titik dengan nilai x positif dan titik dengan nilai y positif. Dengan demikian minimum nilai x dan y positif diambil dan dikurangi menjadi sembilan (setengah atau ketiga bisa cukup). Poin ini tidak dapat menjadi salah satu poin yang ada dan dijadikan asal baru.
Perawatan khusus asal dan sumbu x negatif dapat dihilangkan, karena ada titik yang terletak pada asal baru.
Contoh 3:
Output 3:
Contoh 1 sekarang diurutkan secara berbeda:
Tidak Disatukan:
sumber
GolfScript, 6/13 karakter (jalur terbuka; 49 karakter untuk jalur tertutup)
Kode di atas mengasumsikan bahwa output dapat dalam format yang masuk akal. Jika format output harus sesuai dengan input, versi 13-karakter berikut akan dilakukan:
Penjelasan:
~
mengevaluasi input, mengubahnya menjadi daftar angka;]
mengumpulkan angka-angka ini menjadi sebuah array, dan2/
membagi array ini menjadi dua blok angka, masing-masing mewakili satu titik.$
mengurutkan titik-titik dalam urutan leksikografis, yaitu pertama dengan koordinat x dan kemudian, jika ada ikatan, oleh koordinat y. Sangat mudah untuk menunjukkan bahwa ini akan menjamin bahwa garis-garis yang ditarik di antara titik-titik tidak berpotongan, selama jalur tidak perlu untuk kembali ke awal.Dalam versi 5-karakter,
`
meringkas array yang diurutkan, menghasilkan representasi string asli dari itu (misalnya[[0 0] [0 4] [4 0] [4 4]]
). Dalam versi yang lebih panjang,{" "*n}/
gabungkan koordinat setiap titik dengan spasi, dan tambahkan baris baru.Demo online: versi pendek / versi panjang .
Ps. Inilah solusi 49-char untuk masalah asli, di mana jalur tersebut harus ditutup:
Ia bekerja dengan cara yang mirip dengan solusi Perl Heiko Oberdiek , kecuali bahwa, alih-alih menggunakan fungsi trigonometri, kode ini mengurutkan titik dengan kemiringan ( y - y 0 ) / ( x - x 0 ), di mana ( x 0 , y 0 ) adalah titik dengan x- koordinat terendah (dan y- koordinat terendah , jika beberapa poin terikat untuk x terendah ).
Karena GolfScript tidak mendukung titik mengambang, lereng dikalikan dengan konstanta tetap 9 9 = 387420489. (Jika itu tidak cukup presisi, Anda dapat mengganti
9
dengan99
untuk mengubah pengali menjadi 99 99 ≈ 3,7 × 10 197. ) Ada juga beberapa kode tambahan untuk memutus ikatan (oleh koordinat x ) dan untuk memastikan bahwa, seperti dalam solusi Heiko, poin dengan x = x 0 diurutkan terakhir, dalam urutan menurun oleh koordinat y .Sekali lagi, ini demo online .
sumber
Mathematica, 35
Ini bekerja untuk APAPUN daftar poin unik.
Anda mengatakan "baca dari stdin", jadi untuk Mathematica, saya berasumsi "baca dari keluaran terakhir".
Input (keluaran terakhir):
Keluaran:
Jika input dan output tidak perlu dalam format "baris baru", ini dapat menyusut menjadi 6 karakter:
mengambil output terakhir sebagai input, dengan asumsi output terakhir adalah array 2 dimensi.
Input (keluaran terakhir):
Ouput:
sumber
Sort
melakukan hal yang sama?SortBy
agar saya dapat dengan mudah menyortir sehubungan dengan nilai "x" dan nilai "y".StringSplit
lagi dan menggunakan sintaks infixSort@(s=StringSplit)@%~s~"\n"
.PHP (
175109100 karakter)OK, saya akui, PHP bukan bahasa golf terbaik, tapi saya mencobanya.
Berikut beberapa contoh output:
Apa yang dilakukan adalah menempatkan informasi ke dalam string yang diformat dengan nol sebelumnya.
Kemudian hanya mengurutkan poin secara tekstual.
PS Gagal pada angka di atas
9999
.sumber
Python 2.7, 42B
Tidak bisa lebih sederhana; baca STDIN, urutkan garis, garis cetak. NB Saya menghormati persyaratan I / O yang tepat dari pertanyaan itu, tetapi jika Anda secara manual mengisi STDIN, Anda perlu menekan
CTRL+d
untuk mengakhiri input.sumber