Luas lambung cembung 2D

11

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 , sehingga program terpendek yang benar menang.(x,y)-104104

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.PP(x,y)

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:
masukkan deskripsi gambar di sini

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
Vladimir Reshetnikov
sumber
2
Apakah Anda memiliki test case?
Maltysen
17
Tidak menghitung spasi putih dalam kode golf adalah ide yang buruk, itu mengarah pada pengiriman dengan string spasi putih besar ditambah kode generik untuk mengonversi string menjadi kode dan menjalankannya.
xnor
4
titik tengah yang tepat harus dibulatkan ke bilangan bulat genap terdekat : hanya ingin tahu apa alasan di balik itu?
Arnauld
4
@nwellnhof Benar. Tetapi menegakkan aturan ini hanyalah gangguan bagi bahasa yang tidak melakukannya dengan cara seperti itu (dan saya pikir Python 2 juga tidak bulat-ke-bahkan). Saya tidak berpikir kita harus bulat sama sekali. Segitiga [[0, 0], [1, 1], [0, 1]]benar-benar harus menghasilkan daripada . 01/20
Arnauld
6
Biasanya tantangan itu mandiri, tetapi yang ini tidak. Bisakah Anda menjelaskan apa itu cembung lambung itu, dan bagaimana cara menghitungnya? Atau tunjuk sumber referensi online?
Olivier Grégoire

Jawaban:

9

SQL Server 2012+, 84 byte

SELECT Round(Geometry::ConvexHullAggregate(Geometry::Point(x,y,0)).STArea(),0)FROM A

Memanfaatkan fungsi geometri dan agregat dalam SQL Server. Coordindate berasal dari tabel Adengan kolom xdan y.

MickyT
sumber
9

Java 10, 405 ... tidak cocok lagi; lihat edit histori .. 317 316 bytes

P->{int n=P.length,l=0,i=0,p,q,t[],h[][]=P.clone(),s=0;for(;++i<n;)l=P[i][0]<P[l][0]?i:l;p=l;do for(h[s++]=P[p],q=-~p%n,i=-1;++i<n;q=(t[1]-P[p][1])*(P[q][0]-t[0])<(t[0]-P[p][0])*(P[q][1]-t[1])?i:q)t=P[i];while((p=q)!=l);for(p=i=0;i<s;p-=(t[0]+h[++i%s][0])*(t[1]-h[i%s][1]))t=h[i];return Math.round(.5*p/~(p%=2))*~p;}

-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:

  1. Hitung poin untuk Convex Hull berdasarkan pada koordinat input (menggunakan Jarvis 'Algoritma / Wrapping )
  2. Hitung area Hull Cembung ini
  3. Pembulatan Bankir ..

Untuk menghitung koordinat yang merupakan bagian dari Convex Hull, kami menggunakan pendekatan berikut:

lhalhall

masukkan deskripsi gambar di sini

Adapun kode:

P->{                      // Method with 2D integer array as parameter & long return-type
  int n=P.length,         //  Integer `n`, the amount of points in the input
      l=0,                //  Integer `l`, to calculate the left-most point
      i=0,                //  Index-integer `i`
      p,                  //  Integer `p`, which will be every next counterclockwise point
      q,                  //  Temp integer `q`
      t[],                //  Temp integer-array/point
      h[][]=P.clone(),    //  Initialize an array of points `h` for the Convex Hull
      s=0;                //  And a size-integer for this Convex Hull array, starting at 0
  for(;++i<n;)            //  Loop `i` in the range [1, `n`):
    l=                    //   Change `l` to:
      P[i][0]<P[l][0]?    //   If i.x is smaller than l.x:
       i                  //    Replace `l` with the current `i`
      :l;                 //   Else: leave `l` unchanged
  p=l;                    //  Now set `p` to this left-most coordinate `l`
  do                      //  Do:
    for(h[s++]=P[p],      //   Add the `p`'th point to the 2D-array `h`
        q=-~p%n,          //   Set `q` to `(p+1)` modulo-`n`
        i=-1;++i<n;       //    Loop `i` in the range [0, `n`):
        ;q=               //      After every iteration: change `q` to:
                          //       We calculate: (i.y-p.y)*(q.x-i.x)-(i.x-p.x)*(q.y-i.y), 
                          //       which results in 0 if the three points are collinear;
                          //       a positive value if they are clockwise;
                          //       or a negative value if they are counterclockwise
           (t[1]-P[p][1])*(P[q][0]-t[0])<(t[0]-P[p][0])*(P[q][1]-t[1])?
                          //       So if the three points are counterclockwise:
            i             //        Replace `q` with `i`
           :q)            //       Else: leave `q` unchanged
      t=P[i];             //     Set `t` to the `i`'th Point (to save bytes)
  while((p=q)             //  And after every while-iteration: replace `p` with `q`
             !=l);        //  Continue the do-while as long as `p` is not back at the
                          //  left-most point `l` yet
  // Now step 1 is complete, and we have our Convex Hull points in the List `h`

  for(p=i=0;              //  Set `p` (the area) to 0
      i<s                 //  Loop `i` in the range [0, `s`):
      ;p-=                //    After every iteration: Decrease the area `p` by:
        (t[0]+h[++i%s][0])//     i.x+(i+1).x
        *(t[1]-h[i%s][1]))//     Multiplied by i.y-(i+1).y
    t=h[i];               //   Set `t` to the `i`'th point (to save bytes)
 return Math.round(.5*p/~(p%=2))*~p;}
                          //  And return `p/2` rounded to integer with half-even
Kevin Cruijssen
sumber
1
Mari kita lanjutkan diskusi ini dalam obrolan .
Kevin Cruijssen
6

JavaScript (ES6),  191  189 byte

Menerapkan gerakan Jarvis (alias algoritma pembungkusan hadiah).

P=>(r=(g=p=>([X,Y]=P[p],Y*h-X*v)+(P.map(([x,y],i)=>q=(y-Y)*(P[q][0]-x)<(x-X)*(P[q][1]-y)?i:q,q=P[++p]?p:0,h=X,v=Y)|q?g(q):V*h-H*v))(v=h=0,([[H,V]]=P.sort(([x],[X])=>x-X)))/2)+(r%1&&r&1)/2|0

Cobalah online!

Atau 170 byte tanpa skema pembulatan yang rumit.

Arnauld
sumber
Pembulatan hanyalah herring merah karena dua kali luas selalu selalu bilangan bulat.
Vladimir Reshetnikov
4
@VladimirReshetnikov Karena penasaran: jika Anda tahu pembulatan adalah ikan haring merah, lalu mengapa menambahkannya untuk mengalihkan perhatian dari tantangan yang sebaliknya baik? .. Tidak semua bahasa telah membangun pembulatan Bankir, bahkan bahasa yang tidak terkenal seperti JS dan Java tampaknya. Saya suka tantangan secara umum dan senang menulis jawaban Java saya, tetapi pembulatan dan kurangnya penjelasan tentang Convex Hull adalah untuk membuat tantangan mandiri menahan saya untuk tidak meningkatkannya, tbh .. PS: Maaf @Arnauld melakukan ini sebagai komentar dalam jawaban Anda ..
Kevin Cruijssen
4

R , 85 81 78 byte

function(i,h=chull(i),j=c(h,h[1]))round((i[h,1]+i[j[-1],1])%*%diff(-i[j,2])/2)

Cobalah online!

Mengambil input sebagai matriks 2 kolom - pertama untuk x, kedua untuk y. R's roundsebenarnya menggunakan metode pembulatan bankir, jadi kami cukup beruntung di sini.

saya(xsaya-1+x)(ysaya-1-ysaya)/2

Terima kasih kepada Giuseppe untuk -3 byte.

Kirill L.
sumber
3

[Paket R + sp], 55 byte

function(x)round(sp::Polygon(x[chull(x),,drop=F])@area)

Cobalah di RDRR

Fungsi yang mengambil matriks anx 2 dan mengembalikan area yang dibulatkan. Ini menggunakan sppaket. The drop=Fdiperlukan untuk menangani kasus satu koordinasi. RDRR digunakan untuk demo karena TIO tidak memiliki sppaket.

Nick Kennedy
sumber