Se le proporciona una matriz / lista / vector de pares de enteros que representan coordenadas cartesianas $(x, y)$ de puntos en un plano euclidiano 2D; todas las coordenadas están entre $−10^4$ y $10^4$ , se permiten duplicados. Encuentre el área del casco convexo de esos puntos, redondeado al entero más cercano; un punto medio exacto debe redondearse al entero par más cercano. Puede usar números de coma flotante en cálculos intermedios, pero solo si puede garantizar que el resultado final siempre será correcto. Este es el código de golf , por lo que gana el programa correcto más corto.

El casco convexo de un conjunto de puntos $P$ es el más pequeño conjunto convexo que contiene $P$ . En el plano euclidiano, para cualquier punto único $(x,y)$ , es el punto mismo; para dos puntos distintos, es la línea que los contiene, para tres puntos no colineales, es el triángulo que forman, y así sucesivamente.

Una buena explicación visual de lo que es un casco convexo, se describe mejor como imaginar todos los puntos como clavos en una tabla de madera, y luego estirar una banda elástica alrededor de ellos para encerrar todos los puntos:

Algunos casos de prueba:

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 bytes

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

Utiliza las funciones de geometría y los agregados en SQL Server. Las coordenadas son de tabla Acon columnas xy y.

Java 10, 405 ... ya no encajaba; ver historial de edición .. 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 gracias a @ OlivierGrégoire
-3 bytes gracias a @PeterTaylor
-7 bytes gracias a @ceilingcat

Pruébalo en línea.

O 299 bytes sin redondear .

Explicación:

Hay tres pasos para hacer:

1. Calcule los puntos para el casco convexo en función de las coordenadas de entrada (utilizando el algoritmo / ajuste de Jarvis )
2. Calcule el área de este casco convexo
3. Redondeo del banquero.

Para calcular las coordenadas que forman parte del casco convexo, utilizamos el siguiente enfoque:

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

En cuanto al código:

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

Pruébalo en línea!

JavaScript (ES6),  191  189 bytes

Implementa la marcha Jarvis (también conocido como algoritmo de envoltura de regalos).

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

Pruébalo en línea!

O 170 bytes sin el engorroso esquema de redondeo.

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)

Pruébalo en línea!

Toma la entrada como una matriz de 2 columnas: primero para x, segundo para y. De hecho, R roundutiliza el método de redondeo del banco, por lo que tenemos mucha suerte aquí.

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

Gracias a Giuseppe por -3 bytes.

[Paquete R + sp], 55 bytes

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

Pruébalo en RDRR

Una función que toma la matriz ans 2 y devuelve el área redondeada. Esto usa el sppaquete. Se drop=Fnecesita para manejar un caso de coordenadas. RDRR utilizado para la demostración ya que TIO carece del sppaquete.