On vous donne un tableau / liste / vecteur de paires d'entiers représentant les coordonnées cartésiennes de points sur un plan euclidien 2D; toutes les coordonnées sont comprises entre et , les doublons sont autorisés. Trouvez l'aire de la coque convexe de ces points, arrondie à l'entier le plus proche; un point médian exact doit être arrondi à l'entier pair le plus proche. Vous pouvez utiliser des nombres à virgule flottante dans les calculs intermédiaires, mais uniquement si vous pouvez garantir que le résultat final sera toujours correct. Il s'agit de code-golf , donc le programme correct le plus court l'emporte.$(x, y)$$−10^4$$10^4$

L' enveloppe convexe d'un ensemble de points est l'ensemble convexe le plus petit qui contient . Sur le plan euclidien, pour tout point unique , c'est le point lui-même; pour deux points distincts, c'est la ligne qui les contient, pour trois points non colinéaires, c'est le triangle qu'ils forment, etc.$P$$P$$(x,y)$

Une bonne explication visuelle de ce qu'est une coque convexe est décrite comme imaginant tous les points comme des clous dans une planche de bois, puis en étirant une bande de caoutchouc autour d'eux pour enfermer tous les points:

Quelques cas de test:

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 octets

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

Utilise les fonctions de géométrie et les agrégats dans SQL Server. Les coordonnées proviennent du tableau Aavec les colonnes xet y.

Java 10, 405 ... ne correspondait plus; voir l'historique des modifications .. 317 316 octets

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 octets grâce à @ OlivierGrégoire
-3 octets grâce à @PeterTaylor
-7 octets grâce à @ceilingcat

Essayez-le en ligne.

Ou 299 octets sans arrondi .. .

Explication:

Il y a trois étapes à faire:

1. Calculer les points pour la coque convexe sur la base des coordonnées d'entrée (en utilisant l'algorithme / habillage de Jarvis )
2. Calculez l'aire de cette coque convexe
3. Arrondissement bancaire.

Pour calculer les coordonnées qui font partie de la coque convexe, nous utilisons l'approche suivante:

Réglez le point et sur la coordonnée la plus à gauche. Calculez ensuite le point dans une rotation dans le sens antihoraire; et continuez ainsi jusqu'à ce que nous soyons revenus au point initial . Voici un visuel pour cela:$l$$p$$p$$l$

Quant au 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 octets

Round@*Area@*ConvexHullMesh

Essayez-le en ligne!

JavaScript (ES6),  191  189 octets

Implémente la marche Jarvis (alias algorithme d'emballage cadeau).

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

Essayez-le en ligne!

Ou 170 octets sans le schéma d'arrondi encombrant.

R , 85 81 78 octets

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

Essayez-le en ligne!

Prend l'entrée comme une matrice à 2 colonnes - d'abord pour x, deuxième pour y. R roundutilise en fait la méthode d'arrondi des banquiers, nous avons donc beaucoup de chance ici.

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

Merci à Giuseppe pour -3 octets.

[Package R + sp], 55 octets

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

Essayez-le au RDRR

Une fonction qui prend une matrice anx 2 et renvoie la zone arrondie. Cela utilise le sppackage. Le drop=Fest nécessaire pour gérer le cas à une coordonnée. RDRR utilisé pour la démonstration car TIO n'a pas le sppackage.