Sie erhalten ein Array / eine Liste / einen Vektor von Ganzzahlpaaren, die kartesische Koordinaten $(x, y)$ von Punkten auf einer euklidischen 2D-Ebene darstellen. Alle Koordinaten liegen zwischen $−10^4$ und $10^4$ , Duplikate sind zulässig. Finden Sie den Bereich der konvexen Hülle dieser Punkte, gerundet auf die nächste ganze Zahl; Ein exakter Mittelpunkt sollte auf die nächste gerade ganze Zahl gerundet werden. Sie können Gleitkommazahlen in Zwischenberechnungen verwenden, aber nur, wenn Sie garantieren können, dass das Endergebnis immer korrekt ist. Dies ist Code-Golf , also gewinnt das kürzeste richtige Programm.

Die konvexe Hülle einer Menge von Punkten $P$ ist die kleinste konvexe Menge, die $P$ enthält . Auf der euklidischen Ebene ist es für jeden einzelnen Punkt $(x,y)$ der Punkt selbst; für zwei verschiedene Punkte ist es die Linie, die sie enthält, für drei nicht kollineare Punkte ist es das Dreieck, das sie bilden, und so weiter.

Eine gute visuelle Erklärung dafür, was eine konvexe Hülle ist, lässt sich am besten beschreiben, indem man sich alle Punkte als Nägel in einem Holzbrett vorstellt und dann ein Gummiband um sie spannt, um alle Punkte einzuschließen:

Einige Testfälle:

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

SQL Server 2012+, 84 Byte

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

Verwendet die Geometriefunktionen und -aggregate in SQL Server. Die Koordinaten stammen aus einer Tabelle Amit Spalten xund y.

Java 10, 405 ... passte nicht mehr; Siehe Bearbeitungsverlauf. 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 Bytes dank @ OlivierGrégoire
-3 Bytes dank @PeterTaylor
-7 Bytes dank @ceilingcat

Probieren Sie es online aus.

Oder 299 Bytes ohne Rundung .

Erläuterung:

Es gibt drei Schritte:

1. Berechnen Sie die Punkte für den konvexen Rumpf basierend auf den Eingabekoordinaten (unter Verwendung des Jarvis-Algorithmus / Wrapping ).
2. Berechnen Sie die Fläche dieses konvexen Rumpfes
3. Banker Rundung ..

Um die Koordinaten zu berechnen, die Teil des konvexen Rumpfs sind, verwenden wir den folgenden Ansatz:

$l$$p$$p$$l$

Wie für den Code:

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

Wolfram Language (Mathematica) , 27 Bytes

Round@*Area@*ConvexHullMesh

Probieren Sie es online aus!

JavaScript (ES6),  191  189 Bytes

Implementiert den Jarvis-Marsch (auch bekannt als Geschenkverpackungsalgorithmus).

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

Probieren Sie es online aus!

Oder 170 Bytes ohne das umständliche Rundungsschema.

R , 85 81 78 Bytes

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

Probieren Sie es online aus!

Nimmt die Eingabe als 2-Spalten-Matrix auf - erstens für x, zweitens für y. R verwendet roundtatsächlich die Rundungsmethode des Bankiers, daher haben wir hier ziemlich viel Glück.

$\sum_{i}{(x_{i-1}+x)\cdot(y_{i-1}-y_i)}/2$

Danke an Giuseppe für -3 Bytes.

[R + sp-Paket], 55 Bytes

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

Probieren Sie es bei RDRR

Eine Funktion, die die anx 2-Matrix verwendet und den gerundeten Bereich zurückgibt. Dies verwendet das spPaket. Das drop=Fwird benötigt, um den einen Koordinatenfall zu behandeln. RDRR wird für die Demo verwendet, da TIO das spPaket fehlt .