8
\$\begingroup\$

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 −104 and 104, 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 a code-golf, the shortest correct program (ignoring non-significant whitespace, newlines and comments) wins.

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
\$\endgroup\$

closed as unclear what you're asking by Shaggy, Keeta, Sriotchilism O'Zaic, Chris, Alex A. Apr 16 at 4:32

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ Do you have any test cases? \$\endgroup\$ – Maltysen Apr 14 at 22:12
  • 17
    \$\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 at 22:47
  • 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 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 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\$ – Olivier Grégoire Apr 15 at 12:04
9
\$\begingroup\$

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

Explanation:

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
           (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
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

Wolfram Language (Mathematica), 27 bytes

Round@*Area@*ConvexHullMesh

Try it online!

\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6),  191  189 bytes

Implements the Jarvis march (aka gift wrapping algorithm).

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

Try it online!

Or 170 bytes without the cumbersome rounding scheme.

\$\endgroup\$
  • \$\begingroup\$ Rounding was just a red herring because twice the area is always exactly integer. \$\endgroup\$ – Vladimir Reshetnikov Apr 15 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\$ – Kevin Cruijssen Apr 15 at 14:24
4
\$\begingroup\$

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)

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.

\$\endgroup\$
3
\$\begingroup\$

[R + sp package], 55 bytes

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

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.

\$\endgroup\$

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