# Question
Title: Find the Convex Hull of a set of 2D points
When you hammer a set of nails into a wooden board and wrap a rubber band around them, you get a Convex Hull.

Your mission, should you decide to accept it, is to find the Convex Hull of a given set of 2D points.

---

Some rules:

* Write it as a function, the point's list coordinates (in any format you want) is the argument
* The output must be the list of points in the convex hull listed clockwise or anticlockwise, starting at any of them
* The output list can be in any reasonable format where each point's coordinates are clearly distinguishable. (For example NOT a one dim list { 0.1, 1.3, 4, ...})
* If three or more points in a segment of the convex hull are aligned, only the two extremes should be kept on the output

Sample data:

### Sample 0

Input:

```
{{1, 1}, {2, 2}, {3, 3}, {1, 3}}

```

Output:

```
{{3, 3}, {1, 3}, {1, 1}}

```

(The figures are just illustrative)

### Sample 1

Input:

```
{{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {2.1, 11.1}, {9.5, 14.9},
 {13.2, 11.9}, {10.3, 12.3}, {6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, {5.3, 2.4},
 {8.45, 4.7}, {11.5, 9.6}, {13.8, 7.3}, {12.9, 3.1}, {11, 1.1}}

```

Output:

```
{{13.8, 7.3}, {13.2, 11.9}, {9.5, 14.9}, {6.7, 15.25}, {4.4, 14},
 {2.1, 11.1}, {0.6, 5.1}, {5.3, 2.4}, {11, 1.1}, {12.9, 3.1}}

```

### Sample 2

Input:

```
{{1, 0}, {1, 1}, {1, -1}, {0.68957, 0.283647}, {0.909487, 0.644276},
 {0.0361877, 0.803816}, {0.583004, 0.91555}, {-0.748169, 0.210483},
 {-0.553528, -0.967036}, {0.316709, -0.153861}, {-0.79267, 0.585945},
 {-0.700164, -0.750994}, {0.452273, -0.604434}, {-0.79134, -0.249902},
 {-0.594918, -0.397574}, {-0.547371, -0.434041}, {0.958132, -0.499614},
 {0.039941, 0.0990732}, {-0.891471, -0.464943}, {0.513187, -0.457062},
 {-0.930053, 0.60341}, {0.656995, 0.854205}}

```

Output:

```
{{1, -1}, {1, 1}, {0.583004, 0.91555}, {0.0361877, 0.803816},
 {-0.930053, 0.60341}, {-0.891471, -0.464943}, {-0.700164, -0.750994},
 {-0.553528, -0.967036}}

```

Standard code-golf rules apply. No ad-hoc geometry libraries. Shorter code wins.

**Edit 1**

We are looking for an algorithmic answer here, not a convex hull finder pre-programmed routine like this one in MatLab or this one in Mathematica

**Edit 2**

Answering comments and additional info:

1. You can assume the input list contains the minimum number of points that suits you. But you must ensure proper treatment of aligned (sub)sets.
2. You may find repeated points in the input list
3. The maximum number of points should be limited only by the available memory
4. Re "floating point": You need to be able to process input lists with decimal coordinates as those given in the samples. You *could* do that by using a floating point representation

.

# Answer
> 2 votes
### Ruby, 168 characters

```
C=->q{r=[]
f=m=q.sort[0]
t=-0.5
(_,_,t,*f=q.map{|x,y|a=x-f[0]
b=y-f[1]
[0==(d=a*a+b*b)?9:(-t+e=Math.atan2(b,a)/Math::PI)%2,-d,e,x,y]}.sort[0]
r<<=f)while
!r[1]||f!=m
r}

```

This ruby code also uses the gift wrapping algorithm. The function `C` accepts an array of points and returns the convex hull as array.

Example:

```
>p C[[[4.4, 14], [6.7, 15.25], [6.9, 12.8], [2.1, 11.1], [9.5, 14.9],
     [13.2, 11.9], [10.3, 12.3], [6.8, 9.5], [3.3, 7.7], [0.6, 5.1], [5.3, 2.4],
     [8.45, 4.7], [11.5, 9.6], [13.8, 7.3], [12.9, 3.1], [11, 1.1]]]

[[5.3, 2.4], [11, 1.1], [12.9, 3.1], [13.8, 7.3], [13.2, 11.9], [9.5, 14.9], [6.7, 15.25], [4.4, 14], [2.1, 11.1], [0.6, 5.1]]

```

# Answer
> 2 votes
## Mathematica 151

still work in progress
```
f = For[t = Sort@#; n = 1; l = Pi; a = ArcTan; c@1 = t[[1]],
       n < 2 || c@n != c@1,
       n++,
      (l = a @@ (# - c@n); c[n + 1] = #) & @@
      t[[Ordering[Mod[a@## - l, 2 Pi] & @@ (#2 - #1) & @@@ Tuples@{{c@n}, t}, 1]]]] &

```

testing:

```
ClearAll[a, c, t];
s = {{1, 0}, {0.68957, 0.283647}, {0.909487, 0.644276}, {0.0361877, 0.803816},
     {0.583004, 0.91555}, {-0.748169, 0.210483}, {-0.553528, -0.967036},
     {0.316709, -0.153861}, {-0.79267, 0.585945}, {-0.700164, -0.750994},
     {0.452273, -0.604434}, {-0.79134, -0.249902}, {-0.594918, -0.397574},
     {-0.547371, -0.434041}, {0.958132, -0.499614}, {0.039941, 0.0990732},
     {-0.891471, -0.464943}, {0.513187, -0.457062}, {-0.930053, 0.60341},
     {0.656995, 0.854205}};
f@s
Show[Graphics@Line@Table[c@i, {i, n}],
     ListPlot[{t, Table[c@i, {i, n}]},
     PlotStyle -> {PointSize[Medium], PointSize[Large]},
     PlotRange -> All]]

```

# Answer
> 1 votes
# CoffeeScript, 276:

```
f=($)->z=$[0];e.r=Math.atan2(e.x-z.x,e.y-z.y)for e in $;$.sort((x,y)->(x.r>y.r)-(x.r<y.r));(loop(a=$[i-1]||$[$.length-1];b=$[i];c=$[i+1]||$[0];break if!b;s=(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);break if s<0||!s&&(a.x-b.x)*(b.x-c.x)<0;$.splice i,1))for i in [$.length-1..0];$

```

If the function needs not be accessible, remove `f=` to shave off two more characters.

Input/output is a single array of points, with each point being defined by the `x,y` properties. The input array is modified, as well as returned (if the latter not required, remove the last two characters).

Explanation may be added later.

Test suite (won't work in oldIE):

```
alert JSON.stringify f({x:e[0], y:e[1]} for e in JSON.parse "
{{1, 1}, {2, 2}, ...}
".replace(/{/g,"[").replace(/}/g,"]"))

```

suggested test environment: http://coffeescript.org/

# Answer
> 1 votes
# Python, 209 205 195

```
from math import*
s=lambda(a,b),(c,d):atan2(d-b,c-a)
def h(l):
 r,t,p=[],pi/2,min(l)
 while 1:
    q=min(set(l)-{p},key=lambda q:(s(p,q)-t)%(2*pi));m=s(p,q);r+=[p]*(m!=t);p=q;t=m
    if p in r:return r

```

Uses a gift wrapping algorithm. The result starts with the leftmost point and wraps counter-clockwise.

Example: `h([(1, 1), (2, 2), (3, 3), (1, 3)])` returns `[(1, 3), (1, 1), (3, 3)]`

# Answer
> 0 votes
# C++ (gcc), ~~327~~ 301 bytes

```
#import<bits/stdc++.h>
using V=std::complex<double>;using W=std::deque<V>;W f(W x){V m=x[0],r,c;double v=imag(m),t,g,s=1;for(V a:x)c=m=imag(a-m)>0?a:m,v=fmin(imag(a),v);W p;do{p.push_back(r=c);g=4;for(V a:x)m=c=a!=r?t=std::arg(s*(a-r)),t<g|t==M_PI?g=t,a:c:c;s=imag(m)-v?s:-1;}while(m!=p[0]);return p;}

```

Try it online!

Another implementation of the gift wrapping algorithm. Slightly golfed less:

```
#import<bits/stdc++.h>
using V=std::complex<double>;
using W=std::deque<V>;
W f(W x){
  V m=x[0],r,c;
  double v=imag(m),t,g,s=1;
  // find topmost point
  for(V a:x)
    c=m=imag(a-m)>0?a:m,
    v=fmin(imag(a),v);
  W p;
  do{
    p.push_back(r=c);
    g=4;
    // loop to find the smallest angle t
    for(V a:x)
      m=c=a!=r?
        t=std::arg(s*(a-r)),t<g|t==M_PI?
          g=t,a
        :
          c
      :
        c;
    // are we wrapping over or under?
    s=imag(m)-v?s:-1;
  // loop until we've gone all the way around
  }while(m!=p[0]);
  return p;
}

```

---
Tags: code-golf, geometry
---


title: Please Count ME!

text:
# Question
Title: Please Count ME!
Your task is simple. Post a snippet in any language that if the snippet is repeated n times, will output n in decimal, octal, and hexadecimal, in that order, separated in spaces. n is an integer larger than zero. There is no leading zeroes. Shortest answer wins

## Example

If the snippet is `ABC` then the test case is

```
ABC
1 1 1
ABCABC
2 2 2
ABCABCABCABCABCABCABCABCABC
9 11 9
ABCABCABCABCABCABCABCABCABCABCABCABC
12 14 C
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC
18 22 12

```

# Answer
> 11 votes
# Japt, 12 bytes

```
[°TTs8 TsG]¸

```

*Thanks to @ETHproductions* for saving 2 bytes!

Same as my answer.

# Answer
> 15 votes
## Perl, 30 bytes

```
printf"\r%d %o %x",++$n,$n,$n;

```

Go back to the beginning of the line, increment counter and print counter overwriting the old output.

# Answer
> 12 votes
# JavaScript, ~~54 53 51~~ 47 bytes

*Saved 4 bytes thanks to @user81655*

```
var d=-~d;d+` ${d[b='toString'](8)} `+d[b](16);

```

I'm actually kinda surprised this works.

### Explanation

```
var d=-~d;  // `var` let's `d` not throw an error if it's not defined
            // -~ essentially increments the variable
d+                    // decimal
` ${                  // space character
   d[b='toString'](8) // octal
} `                   // space character
+d[b](16)             // Hexadecimal

```

Try it online

# Answer
> 7 votes
# C++, ~~205~~ 179 bytes

```
int main(){};static int c=1;
#define v(x) A##x
#define u(x) v(x)
#define z u(__LINE__)
#include <cstdio>
class z{public:z(){++c;};~z(){if(c){printf("%d %o %x",--c,c,c);c=0;}}}z;//

```

(No trailing newline - when copied, the first line of the copy and last line of the original should coincide)

Basically, this works by making a sequence of static variables which, on construction, increment a global variable counter. Then, on destruction, if the counter is not 0, it does all its output and sets the counter to zero.

In order to define a sequence of variables with no name conflicts, we use the macro explained as follows:

```
#define v(x) A##x    //This concatenates the string "A" with the input x.
#define u(x) v(x)    //This slows down the preprocessor so it expands __LINE__ rather than yielding A__LINE__ as v(__LINE__) would do.
#define z u(__LINE__)//Gives a name which is unique to each line.

```

which somewhat relies on the quirks of the string processor. We use `z` many times to define classes/variables that will not conflict with each other when copied onto separate lines. Moreover, the definitions which must occur only once are placed on the first line, which is commented out in copies of the code. The `#define` and `#include` statements don't care that they get repeated, so need no special handling.

This code also features undefined behavior in the statement:

```
printf("%d %o %x",--c,c,c)

```

since there are no sequence points, but c is modified and accessed. LLVM 6.0 gives a warning, but compiles it as desired - that `--c` evaluates before `c`. One could, at the expense of two bytes, add the statement `--c;` before the outputs and change `--c` in `printf` to `c`, which would get rid of the warning.

---

Replaced `std::cout` with `printf` saving 26 bytes thanks to a suggestion of my brother.

# Answer
> 6 votes
# CJam, ~~20~~ ~~19~~ 18 bytes

```
];U):USU8bSU"%X"e%

```

*Thanks to @MartinBüttner for golfing off 1 byte!*

Try it online!

### How it works

```
]                  e# Wrap the entire stack in an array.
 ;                 e# Discard the array.
  U                e# Push U (initially 0).
   ):U             e# Increment and save in U.
      S            e# Push a space.
       U8b         e# Convert U to base 8 (array of integers).
          S        e# Push a space.
           U"%X"e% e# Convert U to hexadecimal (string).

```

# Answer
> 4 votes
# , 14 chars / 28 bytes

```
[⧺Ḁ,Ḁß8,Ḁⓧ]ø⬭;

```

`Try it here (Firefox only).`

First answer! Although there are probably better ways to handle this.

# Explanation

```
[⧺Ḁ,Ḁß8,Ḁⓧ]ø⬭; // implicit: Ḁ = 0
[⧺Ḁ,             // increment Ḁ by 1
    Ḁß8,         // octal representation of Ḁ
        Ḁⓧ]     // hex representation of Ḁ
            ø⬭; // join above array with spaces
                 // repeat as desired until implicit output

```

# Answer
> 3 votes
# MATL, 26 bytes

Uses current release (6.0.0). Works on Octave.

```
0$N1+ttYUb8YAb16YA3$XhZc1$

```

### Examples

Once:

```
>> matl 0$N1+ttYUb8YAb16YA3$XhZc1$
1 1 1

```

Twice:

```
>> matl 0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$
2 2 2

```

16 times:

```
>> matl 0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$0$N1+ttYUb8YAb16YA3$XhZc1$
16 20 10

```

### Explanation

The number of elements in the stack is used to indicate how many times we've run the snippet

```
0$         % specify zero inputs for next function, in case this is not the first
           % occurence of the snippet.
N          % number of elements in stack
1+         % add one
tt         % duplicate twice. We now have three copies of the number
YU         % convert to string (decimal)
b8YA       % bubble up number and convert to octal string
b16YA      % bubble up number and convert to hex string
3$XhZc     % join top three elements (strings) with a space
1$         % specify one input for next function. If the program ends here, that next
           % function will be implicit display, so it will print the top of the stack.
           % Else the stack will be left with one element more than at the beginning of
           % the current snippet

```

# Answer
> 2 votes
# TeaScript, ~~21~~ 20 bytes

```
[┼d,dT8),dT16)]j(p);

```

I should make it auto-close on `;`

Try it online

## Explanation

becomes `++`

```
    // Implicit: d = 0
[   // Start array
 ++d,  // Increment d, decimal value
dT8),  // d to base 8
dT16)  // d to base 16
]j(p); // Join by spaces
    // Implicit: Output *last* expression

```

# Answer
> 2 votes
## OCaml, 198 bytes

```
;;open Char
;;(if Sys.argv.(0).[0]='~'then Sys.argv.(0).[0]<-'\000'else Sys.argv.(0).[0]<-chr(1+int_of_char Sys.argv.(0).[0]));let n=1+int_of_char Sys.argv.(0).[0]in Printf.printf"\r%d %o %x"n n n

```

Includes a trailing newline and requires that the filename starts with a tilde (I used `~.ml`; you can run it with `ocaml \~.ml`) because it's the highest-valued standard printable ASCII character. Abuses the fact that all characters in a string are mutable and `Sys.argv.(0).[0]` is the first character in the filename.

It should only work for n = 1 to 126, because the ASCII code for `~` is 126 and I'm adding one to the output. It could be made two bytes shorter if we only want n = 1 to 125. After it's repeated 126 times, it'll cycle back to n = 1.

This is my first ever golf so any comments or improvements would be much appreciated.

Ungolfed version:

```
;; open Char
;; if Sys.argv.(0).[0] = '~'
   then Sys.argv.(0).[0] <- '\000'
   else Sys.argv.(0).[0] <- chr (1 + int_of_char Sys.argv.(0).[0])
;; let n = 1 + int_of_char Sys.argv.(0).[0] in
   Printf.printf "\r%d %o %x" n n n

```

# Answer
> 2 votes
# Vyxal, 12 bytes

```
_&›¥D8τṅ$HWṄ

```

Try it Online!

Try it Online 10 times!

# Answer
> 1 votes
## Perl, 40 bytes

```
$_=<<'';printf"%d %o %x",(1+y/z//)x3;
:

```

There's a final newline behind the colon.

Treats everything after the first line as a here document and counts the `z` in it. For every further copy of the code one `z` is added. We have to add `1` to the count, because there's none for the first snippet (the one that is executed).

If additional output to stderr is allowed, we can omit the 2 single quotes `''` and can get down to 38 bytes. Without the `''` perl emits a warning about a deprecated feature.

# Answer
> 1 votes
## bash, 49 bytes

File `count.bash`:

```
((++n));trap 'printf "%d %o %x\n" $n $n $n' exit;

```

...no trailing newline.

Run:

```
$ bash count.bash
1 1 1
$ cat count.bash count.bash count.bash | bash
3 3 3
$ for i in $(seq 10) ; do cat count.bash ; done | bash
10 12 a

```

# Answer
> 1 votes
# Mathematica, 76 bytes

Note that `n` should have no definitions before.

```
0;If[ValueQ@n,++n,n=1];StringJoin@Riffle[IntegerString[n,#]&/@{10,8,16}," "]

```

Here, the behaviour of `;` is used. The snippet above is one single `CompoundExpression`, however, when a couple of snippets are put together, there is still one `CompoundExpression` as is shown below. (Some unnecessary rearrangements are made.)

```
0;
If[ValueQ@n,++n,n=1]; StringJoin@Riffle[IntegerString[n,#]&/@{10,8,16}," "] 0;
If[ValueQ@n,++n,n=1]; StringJoin@Riffle[IntegerString[n,#]&/@{10,8,16}," "] 0;
If[ValueQ@n,++n,n=1]; StringJoin@Riffle[IntegerString[n,#]&/@{10,8,16}," "]

(* 3 3 3 *)

```

So one cannot make such snippet works if writting explicit `CompoundExpression`. Also, almost everything you like can be put before the first `;` such as `E`, `Pi` or `MandelbrotSetPlot[]`,.

# Answer
> 1 votes
# Python 2, 54 bytes

```
n=len(open(__file__).read())/54;print n,oct(n),hex(n)#

```

No trailing newline. Outputs in the form `1 01 0x1`.

If that's not ok, 56 bytes

```
n=len(open(__file__).read())/56;print"%d %o %x"%(n,n,n)#

```

When pasted in front of each other, the length of the file gets longer by 1 line for each time pasted. The base case starts with 2 lines so you have to subtract 1 from the line length. Computation is suppressed by the comment.

# Answer
> 1 votes
# Python 2.x 140 bytes

This was not meant to be an overly competitive solution, but a method that I found amusing, being for one thing, an attempt at a **multithreaded** code golf.

```
import thread;n=eval("n+1")if"n"in globals()else 1;
def t(c):99**99;print("%s "*3)%(n,oct(n),hex(n))*(c==n)
thread.start_new_thread(t,(n,));

```

Keeps a counter, spawns a thread for each count and if the counter has not changed when the counters timer goes off after a completing an expensive math problem (instead of a timer to save bytes), the formatted string is printed.

Some example configurations and their outputs:

```
import thread;n=eval("n+1")if"n"in globals()else 1;
def t(c):99**99;print("%s "*3)%(n,oct(n),hex(n))*(c==n)
thread.start_new_thread(t,(n,));

Outputs 1 01 0x1

```

and fifteen copy pastes:

```
import thread;n=eval("n+1")if"n"in globals()else 1;
def t(c):99**99;print("%s "*3)%(n,oct(n),hex(n))*(c==n)
thread.start_new_thread(t,(n,));import thread;n=eval("n+1")if"n"in globals()else 1;
def t(c):99**99;print("%s "*3)%(n,oct(n),hex(n))*(c==n)
thread.start_new_thread(t,(n,));import thread;n=eval("n+1")if"n"in globals()else 1;

...

Outputs 15 017 0xf

```

# Answer
> 1 votes
## Perl 5, 31 bytes

```
exit+printf"%d %o %x",(++$-)x3,

```

Uses the same approach as my answer for 'I double the source, you double the output!'.

Try it online!

# Answer
> 1 votes
# APL (Dyalog APL), 30 bytes

Requires `⎕IO` to be `0`.

```
(+,8 16{(⎕D,⎕A)[⍺⊥⍣¯1⊢⍵]}¨⊢)⊃1

```

Attempt This Online!

The main idea is to use an ambivalent function, where the monadic variant would return the result, and the dyadic variant would keep track of the count.

```
(+,8 16{(⎕D,⎕A)[⍺⊥⍣¯1⊢⍵]}¨⊢)⊃1

(+,8 16{(⎕D,⎕A)[⍺⊥⍣¯1⊢⍵]}¨⊢)    # The ambivalent function:
 +                              #   monadic: identity (*); dyadic: left + right
  ,                             #   concatenated with
   8 16{(⎕D,⎕A)[⍺⊥⍣¯1⊢⍵]}¨⊢     #   octal and hexadecimal versions:
       {(⎕D,⎕A)[⍺⊥⍣¯1⊢⍵]}       #     dyadic function to convert int to base-n string:
        (⎕D,⎕A)                 #       digits concatenated to alphabet
               [       ]        #       indexed by
                      ⍵         #         right argument
                 ⊥⍣¯1           #         in base  (returns digit vector, e.g. 42 in base-16 is [2, 10])
                ⍺               #         left argument
                         ¨      #     applied to:
   8                      ⊢     #       8 and right argument,
     16                   ⊢     #       16 and right argument,

# To Summarize:
#   monadic version returns: [arg, oct(arg), hex(arg)]
#   dyadic version returns: [left + right, oct(right), hex(right)]
#     since left argument is always 1 when snippet is repeated, we can simplify it to
#     [1 + right, oct(right), hex(right)]

⊃   # pick first (extracts the current count)
    # when snippet is repeated this would be in front of all the dyadic calls
    # but not in front of the final monadic call

 1  # The initial count

```

Created with the help of Luminespire.

<sup>\*monadic `+` is the conjugate, but can be treated as identity for non complex inputs</sup>

# Answer
> 1 votes
# Awk, 33 bytes

```
{printf v" %o %x",v,v}BEGIN{v++}0

```

Try it online!

This solution abuses the `BEGIN` statements running before anything happens and the `0` at the end to prevent any other patterns from running.

# Answer
> 0 votes
# Ruby, 35 bytes

```
1;$.+=1;$><<"#$. %1$o %1$x"%$.*-~-0

```

Each snippet increments `$.` (which starts as 0 if no files have been read), but only the last outputs anything. `*-~-0` evaluates to `*1`, meaning print the string once, but with concatenation it becomes `*-~-01`, an octal expression evaluating to 0. Since `$><<` doesn't include a trailing newline, printing the empty string means printing nothing.

---
Tags: code-golf
---