Latar Belakang

The convex hull dari jumlah terbatas poin adalah yang terkecil cembung poligon yang berisi semua poin, baik sebagai simpul atau pada interior. Untuk informasi lebih lanjut, lihat pertanyaan ini di PGM yang mendefinisikannya dengan sangat baik .

Memasukkan

N+1Koordinat 2-D ( N >= 3) dilewati STDIN(dengan input golf biasa lainnya diizinkan juga) dalam format berikut (jumlah desimal dapat bervariasi tetapi Anda dapat menganggapnya tetap "masuk akal" dan setiap angka dapat direpresentasikan sebagai pelampung):

0.00;0.00000
1;0.00
0.000;1.0000
-1.00;1.000000

Keluaran

Nilai kebenaran dicetak ke STDOUT(atau setara) jika titik pertama dalam daftar ( (0.00;0.00000)dalam contoh di atas) adalah lambung cembung dari titik N lainnya, dan nilai palsu sebaliknya.

Ini adalah kode-golf , jadi solusi terpendek dalam byte menang.

• Border case : Anda dapat mengembalikan nilai apa pun (tapi jangan crash) jika titiknya terletak di perbatasan cembung cembung (yaitu di samping atau di sudut di perbatasan luar lambung), karena ini merupakan probabilitas nol acara (di bawah probabilitas yang masuk akal).

• Forbidden : apa saja (bahasa, operator, struktur data, built-in atau paket) yang ada hanya untuk memecahkan masalah geometris (misalnya ConvexHull Mathematica ). Alat matematika tujuan umum (vektor, matriks, bilangan kompleks, dll.) Diizinkan.

Tes

• Harus kembali TRUE: spiralTest1-TRUE , squareTest1-TRUE
• Harus kembali FALSE: spiralTest2-FALSE , squareTest2-FALSE

J, 40 39 34 byte

3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

Fungsi diad anonim, mengambil titik, p , sebagai salah satu argumennya, dan daftar titik, P , sebagai argumen lain (tidak masalah argumen mana), dan mengembalikan 0atau 1, jika p berada di luar atau di dalam lambung cembung P , masing-masing. Titik p , dan titik dalam P , diambil sebagai bilangan kompleks.

Contoh

  is_inside =: 3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

  0.5j0.5  is_inside  0j0 0j1 1j0 1j1
1
  1.5j0.5  is_inside  0j0 0j1 1j0 1j1
0

atau...

Python 2, berfungsi, 121 103, program lengkap, 162

Python 3, 149 byte

import sys,cmath as C
p,q,*P=[complex(*eval(l.replace(*";,")))for l in sys.stdin]
A=[C.phase((r-p)/(q-p+(q==p)))for r in P]
print(max(A)-min(A)>C.pi)

Mengambil input, dalam format yang sama dengan posting asli, melalui STDIN, dan mencetak nilai boolean yang menunjukkan apakah p ada dalam cembung cembung P

Penjelasan

Program menguji apakah perbedaan antara sudut maksimum dan minimum (ditandatangani) antara titik r dalam P , p , dan titik arbitrer tetap q dalam P (kami hanya menggunakan titik pertama dalam P ), kurang dari 180 °. Dengan kata lain, itu menguji apakah semua titik di P terkandung dalam sudut 180 ° atau kurang, sekitar p . p adalah dalam cembung lambung P jika dan hanya jika kondisi ini salah.

Dengan biaya beberapa byte lagi, kita dapat menggunakan metode serupa yang tidak mengharuskan kita menghitung sudut secara eksplisit: Perhatikan bahwa kondisi di atas setara dengan mengatakan bahwa p berada di luar cembung cembung P jika dan hanya jika ada garis l sampai p , sedemikian sehingga semua titik dalam P berada di sisi yang sama dengan l . Jika garis seperti itu ada, maka ada juga garis yang merupakan insiden pada satu (atau lebih) titik di P (kita dapat memutar l sampai menyentuh salah satu titik di P. )

Untuk (tentatif) menemukan baris ini, kita mulai dengan membiarkan l menjadi garis melalui p dan titik pertama di P . Kami kemudian mengulangi sisa poin dalam P ; jika salah satu poin berada di sebelah kiri l (kami menganggap beberapa arah di seluruh, kiri atau kanan tidak terlalu penting,) kami mengganti l dengan garis yang melewati p dan titik itu, dan melanjutkan. Setelah kita mengulangi semua P , jika (dan hanya jika) p berada di luar cembung cembung, maka semua titik dalam P harus di sebelah kanan (atau pada) l . Kami memeriksa bahwa menggunakan pass kedua atas poin di P.

Python 2, 172 byte

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=reduce(lambda*x:x[C(*x)],P)
print any(C(l,q)for q in P)

Sebagai alternatif, untuk melakukan hal yang sama dalam satu lintasan, biarkan ke-kiri- menjadi realsi antara dua titik, q dan r , dalam P , sedemikian sehingga q ada di kiri r jika q ada di kiri dari garis yang melewati p dan r . Perhatikan bahwa to-the-kiri dari sebuah hubungan order pada P jika dan hanya jika semua poin di P berada di sisi yang sama dari beberapa garis yang melewati p , yaitu, jika p adalah luar lambung cembung P . Prosedur yang dijelaskan di atas menemukan titik minimum dalam Pwrt urutan ini, yaitu, "paling kiri" titik dalam P . Alih-alih melakukan dua lintasan, kita dapat menemukan maksimum (yaitu, titik "paling kanan"), serta minimum, poin dalam P wrt urutan yang sama dalam satu lintasan, dan memverifikasi bahwa minimum berada di sebelah kiri maksimum, yaitu, secara efektif, bahwa di sebelah kiri adalah transitif.

Ini akan bekerja dengan baik jika p berada di luar convex hull dari P , dalam hal mana ke-kiri-sebenarnya adalah relasi urutan, tetapi dapat pecah ketika p berada di dalam convex hull (misalnya, cobalah mencari tahu apa yang akan terjadi jika kita menjalankan algoritma ini di mana titik dalam P adalah simpul dari segi lima biasa, berjalan berlawanan arah jarum jam, dan p adalah pusatnya.) Untuk mengakomodasi, kami sedikit mengubah algoritme: Kami memilih titik q dalam P , dan membagi dua P sepanjang garis yang melewati p dan q (yaitu, kita mempartisi P di sekitar qwrt to-the-left-of.) Kita sekarang memiliki "bagian kiri" dan "bagian kanan" P , masing-masing terkandung dalam setengah pesawat, sehingga ke-kiri-dari adalah relasi urutan pada masing-masing; kami menemukan minimum bagian kiri, dan maksimum bagian kanan, dan membandingkannya seperti dijelaskan di atas. Tentu saja, kita tidak perlu membagi dua P secara fisik , kita dapat dengan mudah mengklasifikasikan setiap titik dalam P karena kita mencari minimum dan maksimum, dalam satu lintasan.

Python 2, 194 byte

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=r=P[0]
for q in P:
 if C(P[0],q):l=q*C(l,q)or l
 elif C(q,r):r=q
print C(l,r)

Oktaf, 82 72 byte

d=dlmread(0,";");i=2:rows(d);~isna(glpk(i,[d(i,:)';~~i],[d(1,:)';1]))&&1

Idenya adalah untuk memeriksa apakah program linear min {c'x: Ax = b, e'x = 1, x> = 0} memiliki solusi, di mana e adalah vektor dari semua yang ada, kolom A adalah koordinat dari titik awan, dan b adalah titik uji, dan c adalah arbitrer. Dengan kata lain, kami mencoba untuk mewakili b sebagai kombinasi cembung dari kolom A.

Untuk menjalankan skrip, gunakan octave -f script.m <input.dat

R, 207 byte

d=read.csv(file("stdin"),F,";")
q=function(i,j,k)abs(det(as.matrix(cbind(d[c(i,j,k),],1))))
t=function(i,j,k)q(i,j,k)==q(1,i,j)+q(1,i,k)+q(1,j,k)
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

Script mengambil input dari STDIN, mis Rscript script.R < inputFile.

Ini menghasilkan semua segitiga dari Ntitik terakhir (baris terakhir, apply(combn(...) dan memeriksa apakah titik pertama dalam segitiga menggunakan tfungsi.

tmenggunakan metode area untuk memutuskan apakah Uada di ABC: (menulis (ABC)untuk area ABC) Uada di ABCiff (ABC) == (ABU) + (ACU) + (BCU). Selain itu, area dihitung menggunakan rumus determinan (lihat di sini untuk demo yang bagus dari Wolfram).

Saya menduga solusi ini lebih rentan terhadap kesalahan numerik daripada yang lain, tetapi berfungsi pada kasus pengujian saya.

R, 282 byte

d=read.csv(file("stdin"),F,";")
p=function(a,b)a[1]*b[1]+a[2]*b[2]
t=function(a,b,c){A=d[a,];
U=d[1,]-A
B=d[b,]-A
C=d[c,]-A
f=p(C,C)
g=p(B,C)
h=p(U,C)
i=p(B,B)
j=p(U,B)
k=f*i-g*g
u=i*h-g*j
v=f*j-g*h
min(u*k,v*k,k-u-v)>0}
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

Script mengambil input dari STDIN, mis Rscript script.R < inputFile.

Ini menghasilkan semua segitiga dari Ntitik terakhir (baris terakhir, apply(combn(...) dan memeriksa apakah titik pertama dalam segitiga menggunakan tfungsi.

tmenggunakan metode barycentric untuk memutuskan apakah Uberada di ABC: (menulis XYuntuk Xke Yvektor) karena (AB,AC)merupakan dasar untuk pesawat (kecuali untuk kasus-kasus merosot di mana A, B, C selaras), AUdapat ditulis sebagai AU = u.AB + v.ACdan Udalam IFF segitiga u > 0 && v > 0 && u+v < 1. Lihat misalnya di sini untuk penjelasan yang lebih terperinci dan bagan interaktif yang bagus.NB: untuk menyimpan beberapa karakter dan menghindari kesalahan DIV0, kami hanya menghitung jalan pintas ke udan vdan tes yang dimodifikasi ( min(u*k,v*k,k-u-v)>0).

Hanya operator matematika yang digunakan adalah +, -, *, min()>0.