[Question]
  [
[proposed by @Adám in chat](https://chat.stackexchange.com/transcript/message/62831208#62831208)
Given an even number of finite points return a line \$y=mx+b\$ that evenly splits the points on both sides.
## Specs
* Take a list of distinct points \$(x,y)\$ (or a list of x-coordinates and a list of y-coordinates), output a possible \$(m,b)\$ pair
* Half of the points should be true for \$y>mx+b\$, the other half should be true for \$y<mx+b\$
* All \$x, y\$ pairs are integers
* There will always exist a line \$y=mx+b\$ which divides the points, in which \$m\$ and \$b\$ are integers, but you can output rationals
## Test cases
```
[(1, 1), (-1, -1)] -> -1, 0
[(0, 0), (2, -3)] -> 1, -3
[(3, 4), (0, 0), (-2, -6), (4, -5), (-2, 1), (-23, -18)] -> (-2, -1)]
```
  
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), ~~22~~ 21 bytes
```
Þn:Ẋλ⁰∩YṘ÷*+-±₌A∑¬∧;c
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIiLCIiLCLDnm464bqKzrvigbDiiKlZ4bmYw7cqKy3CseKCjEHiiJHCrOKIpztjIiwiIiwiWyg1LCAyKSwgKDQsIDMpXSJd)
*-1 byte:* Fixed a bug and saved a byte thanks to *@KevinCruijssen*
Simply tries all integer pairs until one works.
```
Þn                      # all integers
  :                     # duplicate
   Ẋ                    # cartesian product
    λ               ;c  # find first pair [m,b] such that:  
     ⁰∩                 #   transposed input [x-coords, y-coords]
       Y                #   interleave [m, x-coords, b, y-coords]
        Ṙ               #   reverse [y-coords, b, x-coords, m]
         ÷              #   push each to stack
          *             #   multiply
           +            #   add
            -           #   subtract
             ±          #   sign
              ₌A∑¬∧     #   are all non zero and is the sum 0?
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), ~~39~~ 38 bytes
```
`,Xrk]XJxXIx0G"1@g0Jh-lIh&v0&|ZS/+]]IJ
```
Input is a cell array of 1×2 vectors. Output is `m`, then `b`.
This produces a random output among all valid outputs, possibly different in each run. Running time is also random, but the code ends in finite time with probability 1.
[**Try it online!**](https://tio.run/##y00syfn/P0Enoig7NsKrIsKzwsBdydAh3cArQzfHM0OtzECtJipYXzs21tPr///qaGMdBZNYHYVoAx0FAxCta6SjoGsGYpkAGaYwIUMIA6ha19AithYA "MATL – Try It Online")
Or try at [**MATL Online**](https://matl.io/?code=%60%2CXrk%5DXJxXIx0G%221%40g0Jh-lIh%26v0%26%7CZS%2F%2B%5D%5DIJ+++++++++%25+required+code%0AG%21gt1Z%29XKw2Z%291j%2a%2B%27%2a%27%26XG1%241%231ZG2%3A%29tI%2aJ%2Bl3ZG%26XG++%25+plot+points+and+line&inputs=%7B%5B3%2C+4%5D%2C+%5B0%2C+0%5D%2C+%5B-2%2C+-6%5D%2C+%5B4%2C+-5%5D%2C+%5B-2%2C+1%5D%2C+%5B-23%2C+-18%5D%7D&version=22.7.4) including a plot with the points and the solution line.
### How it works
The code randomly picks integer values for `m` and `b` until a solution is found. The choice of each of those two values follows a *normalized Gaussian distribution* rounded down. This ensures that each integer pair has a non-zero probability, and will eventually be tried with probability 1.
For each `m` and `b`, the value `b` is first subtracted from the *y*-coordinate of all points. This has the effect of shifting the line vertically so now it passes through the origin with direction given by the vector `[1, m]`.
To test which side of the line a point `[x, y]` is in, the *vector product* of `[1, m]` and `[x, y]` is computed. This is equivalent to the *determinant* of the 2×2 matrix formed by those vectors. The *sign* of the result indicates the side, with a 0 meaning that the point is exactly on the line. Thus, a line is valid if and only if the sum of all signs is 0 and no sign was 0. This is tested by computing the sum of the *inverses* of the signs and checking if it is 0 (if a sign is 0 the sum will give an infinite result).
[Answer]
# [Python](https://www.python.org), 54 bytes
```
lambda L:[m:=1+L.ptp(),sorted(L@[-m,1])[len(L)//2]-.5]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=NVBBasMwELz7FXvcTVaO7CYhGAx9gE65qiIkJE4NkSxkB-J-pZdAaf_Ut_RSqW4OywzDzDLM-5cfh9fO3T-a-uXzOjRi872-7O3huAdVaVvVxVzlfvBI3HdhOB1RPWthuTCkLyeHihaL0oh8Zf7TP03oLLir9SO01scMhB2HvTt2lvv27LKmC6CgdYAZaHxiWBIDSgaZUJQMYp3YMpLVQyomEt2i2JDhDKaXeYLWDSgKKTkdlpJLoujQWrIoDEeQJkWoysDyAWpoMOy0MpSBDykd1ci3tcbbX0m0s9v8IEYiSHVvPKbCyjz8_dWinr21HmdbMjquUdeSpgnu9wl_AQ)
Takes an Nx2 NumPy array.
Slightly longer but more readable version:
# [Python](https://www.python.org), 58 bytes
```
lambda L:[m:=1+ptp(L),median(L@[-m,1])]
from numpy import*
```
[Attempt This Online!](https://ato.pxeger.com/run?1=ZVDBSsQwFLz3K94x6b5IUldZCgE_IKe9xrC01K4Bk4ZsC62_4qUg-k9-ixcT6548PGZ4b-YxzNtnWMbnwa_vvXz8mMaeHb7ql8a1XQOq1q6WYhfGQBRF99TZxhP1oJlDYagp-jg48JMLC1gXhjiWfx--_10gnjA2vhscXuzZF_0QQYH1QArQ5BZhTxEIR-AZWYXA7jPbJ3J3XYmNJDUTB2qwgO3lTQbrR8IE55iHVBwrSpNCa45MGEzATbbQugCHLUjoSTxpZWgBIWZ32iZ-lJrMvyGJK-ddyxZKIcedccmBlbnqL5Mjuny1gZRHanSqREpOtwrWdcMf)
### How?
This chooses a slope larger than the "diameter" of the given point cloud to avoid any ties.
[Answer]
# [Python](https://www.python.org), 169 bytes
```
def g(P,*p):
 a,b,c=p or[0]*3
 for i,(x,y)in enumerate(P):l=2*(i<len(P)/2)-1;q=a*x+b*y+c;v=(q*l<=0)*(l-q);a+=v*x;b+=v*y;c+=v;z=a,b,c
 return z!=p and g(sorted(P),*z)or z
```
[Attempt This Online!](https://ato.pxeger.com/run?1=Nc49DoIwHAXwnVPUrf1TIuJiKL0Du3EoUJQEC9RCaK_iwqKJR_I21q_p5S3v_a733ppTp5blNpo62j0flazREecUepIGSNCClrxHnd7HB9gGqO40aiieqSWNQlKNZ6mFkTgnacsTwE3WSuXbOiHRhg1cwBwWYMOSTRwP0GY8JoDbaCBMhHyCmRXvsKz0wRz_HAZISzNqhdzKfwtVedGl00ZWfpmCIx7hvuCf--9_AQ)
Sort of cheating, since it outputs the values \$(a,b,c)\$ defining the line \$ax+by+c=0 \Rightarrow y = (-ax-c)/b = -\frac{a}{b}x - \frac{c}{b}\$.
Explanation to be added later, but in brief:
* Sorts the points, then says that the first half of the list is in one group and the second half is in another (I believe this always produces two sets which are separable, but I haven't proved it).
* Uses a perceptron algorithm to find the line which classifies those points.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 30 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
A lot of bytes, and extra computation, to effectively break on the first found solution :(
```
×Ṛ_+⁸ṪṠ
ŒRṗ2çⱮS¬ȧẠƲ¥Ƈ
1ç1#Ṫç⁸Ḣ
```
A monadic Link that accepts a list of the coordinates that yields a pair of integers, \$[m, b]\$.
**[Try it online!](https://tio.run/##y0rNyan8///w9Ic7Z8VrP2rc8XDnqoc7F3AdnRT0cOd0o8PLH21cF3xozYnlD3ctOLbp0NJj7VyGh5cbKgOVAeWAyncs@v//f7SGgY6Bpo6GIZCMBQA "Jelly – Try It Online")**
### How?
```
×Ṛ_+⁸ṪṠ - Link 1 side of the line: L=[m, b]; P=[x, y]
×       - (L) multiply (P) -> [mx, by]
 Ṛ      - reverse (that)   -> [by, mx]
  _     - subtract (P)     -> [by-x, mx-y]
    ⁸   - chain's left argument = L
   +    - add              -> [by-x+m, mx-y+b]
     Ṫ  - tail             -> mx-y+b = (mx+b)-y
      Ṡ - sign -> 1 (below), 0 (on), or -1 (above)
ŒRṗ2çⱮS¬ȧẠƲ¥Ƈ - Link 2 find solutions: integer k, coordinates C
ŒR            - span-range -> [-abs(k)..abs(k)]
  ṗ2          - second Cartesian power -> all [m,b] using values from -k to k
            Ƈ - filter keep those for which:
           ¥  -   last two links as a dyad - f(L=[m,b], C)
     Ɱ        -     map (across each coordinate pair, P, in C) with:
    ç         -       call Link 1 - f(L, P) -> side of the line
          Ʋ   -     last four links as a monad - f(A=that):
      S       -       sum (A)
       ¬      -       logical NOT (that)
         Ạ    -       all (A)?
        ȧ     -       logical AND
1ç1#Ṫç⁸Ḣ - Link: coordinates C
1        - set the left argument to one
  1#     - find the first one integers, k (incrementing), for which:
 ç       -   call Link 2 - f(k, C) -> empty lists are falsey
    Ṫ    - tail -> get the k value found
      ⁸  - chain's left argument = C
     ç   - call Link 2 - f(found k, C)
       Ḣ - head (that)
```
[Answer]
# Python3, 268 bytes:
```
import math as M,statistics as S
K=lambda p,x,y:(m:=M.tan(S.median([M.atan2(Y-y,X-x)for X,Y in p])),y-m*x)
def v(p,x,y):
 t=[0,0]
 for X,Y in p:t[Y<(x*X+y)]+=1
 return t[0]==t[1]
f=lambda p:[R for t in p for T in p-{t} if v(p,*(R:=K(p,(t[0]+T[0])/2,(t[1]+T[1])/2)))][0]
```
[Try it online!](https://tio.run/##XY7NboMwEITvfoo9esFOMaRVhOoniLgkOSRCHNwSFEvlR7CtQFGendpEaaterG9mdmfdTXRpm2TT9fNs667tCWpDFzADZGIgQ3Yg@z54vWdb/WHqt9JAJ0YxpbxOdbYi0/D9qj6X1kGerYwzYn6SkzjKEau2h6M4gW2gKxDFJOtgRFaeK/jiSw2mDEjnkYgKBn/HU8pPr3wMjuGERagVg/5Mn30DlEeF1pSrglU/P0rz3bJNy@6ChwXllW5g7@cCvkv11gH3HeHBPfgUe6W8Ul4hYuH8uettQ7ziV64EKBTApQOp8IbIfsNIQOTD2GXJvywRsPbZY0b6oRdPawfPD@teHie@feMr5m8)
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 39 bytes
```
≔Ｅθ↨ι⁰η≔⊕⁻⌈η⌊ηηＷ⁻Ｅθ↨κ±ηυ⊞υ⌊ιＩ⟦η⁻§υ⊘Ｌυ·⁵
```
[Try it online!](https://tio.run/##RY@xDoIwEIZ3n6LjNSmGaJyc0EUSMeyEocELbSxVaYu8fT0Iyna5//u/3DVK9s1Tmhgz53RroZAveAt2kg5BC5ZyLpjix80S57bpsUPr8Q6FtsFRYdRd6EARSJtl/tU@Shtkf3R1PwS7YSs9LnDgnJXBKQirRnMylL22Hs7SeajUnJEp87m94zjBF2kGOuaKtvXUnmXp9sBrKsdYVZBOXwgGO8GSPa/rmAzmCw "Charcoal – Try It Online") Link is to verbose version of code. Explanation: Inspired by @loopywalt's NumPy answer.
```
≔Ｅθ↨ι⁰η≔⊕⁻⌈η⌊ηη
```
Calculate `m` as the incremented maximum `y` extent between any two points.
```
Ｗ⁻Ｅθ↨κ±ηυ⊞υ⌊ι
```
Calculate and sort what the `y`-intercepts would be for lines of gradient `m` that pass through each point. (These must all be different due to the size of `m` calculated above.)
```
Ｉ⟦η⁻§υ⊘Ｌυ·⁵
```
Output `m` and a `y`-intercept that divides the set of points into two.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 29 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
∞<D(.ιæ2ù.ΔIø.ιR`*+-DĀPs.±O_*
```
Port of [*@AndrovT*'s Vyxal answer](https://codegolf.stackexchange.com/a/257880/52210).
[Try it online](https://tio.run/##yy9OTMpM/f//Ucc8GxcNvXM7Dy8zOrxT79wUz8M7gLygBC1tXZcjDQHFeoc2@sdr/f8fHW2sYxKrE22gYwAkdY10dM2AtImOrimEawimjHV0DS1iYwE) or [verify all test cases](https://tio.run/##yy9OTMpM/V9WeWilvZLCo7ZJCkr2/x91zLNx0dA7t/PwMqPDO/XOTTm07vAOIDcoQUtb1@VIQ0Cx3qGN/vFa/2t1/kdHRxvqGMbqROsa6ugaxsbqKERHG@gYAAWMdHSNIXxjHRMgHyKqCxQ2A9ImOrqmEC5Ys5ExULdFbGwsAA).
**Explanation:**
```
∞           # Push an infinite positive list: [1,2,3,...]
 <          # Decrease it to a non-negative list: [0,1,2,...]
  D(        # Push a negative copy: [0,-1,-2,...]
    .ι      # Interleave the lists together: [0,0,1,-1,2,-2,...]
      æ     # Get the powerset of this list
       2ù   # Only keep all pairs: [[0,0],[0,1],[0,1],[0,-1],[0,-1],[1,-1],[0,2],...]
.Δ          # Pop and keep the first pair [m,b] that's truthy for:
  Iø        #  Push the transposed/zipped input-list, swapping its rows/columns
    .ι      #  Interleave it with the current pair: [m,x-coords,b,y-coords]
      R`    #  Push it in reversed order to the stack
        *   #  Multiply m to the x-coords
         +  #  Add b to each
          - #  Subtract each from the y-coords
  DĀPs.±O_* #  Check that there is an equal amount of positive/negative values and no 0s:
  D         #   Duplicate the list
   Ā        #   != 0 check on each
    P       #   Product to check all are truthy
     s      #   Swap so the list is at the top again
      .±    #   Signs of each integer
        O   #   Sum them together
         _  #   ==0 check
          * #   Check if both are truthy
            # (after which the found [m,b]-pair is output implicitly)
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 162 bytes
```
Catch[n=0;While[True,m=(-1)^n⌊(n+1)/2⌋;a=#[[2]]-m#[[1]]&/@#1;Do[If[Values@CountsBy[b-a,Sign]=={#2,#2},Throw[{m,b}]],{b,Range@@MinMax@a}];n++]]&[#,Length@#/2]&
```
[Try it online!](https://tio.run/##NYzRSsMwGEZfpRAYG/1DmzhFKIHgvBEciA69CBHSkTaB9S90KSohL6B7yr1I7RCvzuHj8HUmONuZ4PdmasS0MWHvFIqyenP@YNVuGC10YknZ6h3Pp@8l5mxV8PPppzKCKMW1pt1MpvWikIRV9716aNSrOYz2KDf9iOF496VqauDFt6iFiIQD4Ql2bug/VOygTlpDrOHZYGul3Hrcmk9pkq4wz@dbReDRYhucJAXXi@lp8BhkI2O8gmydIIslZOWFlENGby62nuX6f2J/MteU3aY0/QI "Wolfram Language (Mathematica) – Try It Online")
Start from \$m = 0\$. Going through \$0, -1, 1, -2, 2, …\$ ([OEIS A130472](https://oeis.org/A130472))  
Find \$b\_{min}\$ and \$b\_{max}\$ that bounded array of points with given \$m\$ (here \$m = -2\$):
[![enter image description here](https://i.stack.imgur.com/8ngJK.jpg)](https://i.stack.imgur.com/8ngJK.jpg)
Scan from \$b\_{min}\$ to \$b\_{max}\$. If the test line halves the array and does not pass through any point then throw-catch `{m,b}`. Else test the next \$m\$.  
Fast and reliable algorithm, find \$m\$ closest to \$0\$, so solution for the last test case is `{0, -4}` (but we can start from any other value).
Ungolfed version:
```
halfline[pts_] := With[{h = Length@pts/2},
    n = 0;
    Catch[
     While[True,
      m = (-1)^n ⌊(n + 1)/2⌋;
      arr = #[[2]] - m #[[1]] & /@ pts;
      Do[
       If[Values@CountsBy[b - arr, Sign] == {h, h}, 
         Throw[{m, b}]
         ]
       , {b, Range @@ MinMax@arr}];
      n++
      ]
     ]
    ] /; MatrixQ[pts, IntegerQ];
```
]