You are given an array/list/vector of pairs of integers representing cartesian coordinates \$(x, y)\$ of points on a 2D Euclidean plane; all coordinates are between \$−10^4\$ and \$10^4\$, duplicates are allowed. Find the area of the convex hull of those points, rounded to the nearest integer; an exact midpoint should be rounded to the closest even integer. You may use floating-point numbers in intermediate computations, but only if you can guarantee that the final result will be always correct. This is , so the shortest correct program wins.

The convex hull of a set of points \$P\$ is the smallest convex set that contains \$P\$. On the Euclidean plane, for any single point \$(x,y)\$, it is the point itself; for two distinct points, it is the line containing them, for three non-collinear points, it is the triangle that they form, and so forth.

A good visual explanation of what a convex hulls, is best described as imagining all points as nails in a wooden board, and then stretching a rubber band around them to enclose all the points:
enter image description here

Some test cases:

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
  • 18
    \$\begingroup\$ Not counting whitespace in code golf is a bad idea, it leads to submissions with massive strings of whitespace plus generic code to convert the string to code and execute it. \$\endgroup\$
    – xnor
    Apr 14, 2019 at 22:47
  • 3
    \$\begingroup\$ So if someone can just make a whitespace solution... \$\endgroup\$
    – att
    Apr 15, 2019 at 0:08
  • 4
    \$\begingroup\$ an exact midpoint should be rounded to the closest even integer: just wondering what's the reasoning behind that? \$\endgroup\$
    – Arnauld
    Apr 15, 2019 at 8:47
  • 4
    \$\begingroup\$ @nwellnhof True. But enforcing this rule is just an annoyance for languages that don't do it that way (and I think Python 2 doesn't round-to-even either). I don't think we should round at all anyway. The triangle [[0, 0], [1, 1], [0, 1]] really should yield \$1/2\$ rather than \$0\$. \$\endgroup\$
    – Arnauld
    Apr 15, 2019 at 11:49
  • 6
    \$\begingroup\$ Usually challenges are self-contained, but this one isn't. Could you explain what a convex hull is, and how to compute it? Or point to some reference online resource? \$\endgroup\$ Apr 15, 2019 at 12:04

6 Answers 6


SQL Server 2012+, 84 bytes

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

Makes use of the geometry functions and aggregates in SQL Server. Coordindates are from table A with columns x and y.


Java 10, 405 ...didn't fit anymore; see edit history.. 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 thanks to @OlivierGrégoire
-3 bytes thanks to @PeterTaylor
-7 bytes thanks to @ceilingcat

Try it online.

Or 299 bytes without rounding...


There are three steps to do:

  1. Calculate the points for the Convex Hull based on the input-coordinates (using Jarvis' Algorithm/Wrapping)
  2. Calculate the area of this Convex Hull
  3. Banker's rounding..

To calculate the coordinates that are part of the Convex Hull, we use the following approach:

Set point \$l\$ and \$p\$ to the left-most coordinate. Then calculate the next point \$p\$ in a counterclockwise rotation; and continue doing so until we've reached back at the initial point \$l\$. Here a visual for this:

enter image description here

As for the 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
                          //       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


Try it online!


JavaScript (ES6),  191  189 bytes

Implements the Jarvis march (aka gift wrapping algorithm).


Try it online!

Or 170 bytes without the cumbersome rounding scheme.

  • \$\begingroup\$ Rounding was just a red herring because twice the area is always exactly integer. \$\endgroup\$ Apr 15, 2019 at 14:00
  • 4
    \$\begingroup\$ @VladimirReshetnikov Out of curiosity: if you knew rounding was a red herring, then why add it to distract from the otherwise good challenge?.. Not all languages have builtin Banker's rounding, not even well-known languages like JS and Java apparently. I like the challenge in general and enjoyed writing my Java answer, but the rounding and lack of explanation what Convex Hull is to make the challenge self-contained refrained me from upvoting it, tbh.. PS: Sorry @Arnauld to do this as a comment in your answer.. \$\endgroup\$ Apr 15, 2019 at 14:24

R, 85 81 78 bytes


Try it online!

Takes input as a 2-column matrix - first for x, second for y. R's round actually uses banker's rounding method, so we are quite lucky here.

The code uses a built-in function to determine, which points form the convex hull, and then applies the standard formula \$\sum_{i}{(x_{i-1}+x)\cdot(y_{i-1}-y_i)}/2\$ to get the polygon surface area.

Thanks to Giuseppe for -3 bytes.


[R + sp package], 55 bytes


Try it at RDRR

A function which takes a n x 2 matrix and returns the rounded area. This uses the sp package. The drop=F is needed to handle the one co-ordinate case. RDRR used for demo since TIO lacks the sp package.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.