[Question]
  [
# Challenge
## Premise
Bob lost1 Alice's precious grand piano. Big mistake. Alice has now stolen Bob's low-orbit ion cannon.
Alice refuses to just make up with Bob, so let's help her give him a *light tap* on the roof. Suppose that from the top Bob's house looks like a lattice polygon, where all points have integer coordinates...
1. So he says.
## Task
**Input:** an \$n\times2\$ matrix of integers (where \$3\leq n\leq16\$) representing the coordinates of the points of an \$n\$-gon, given in the order in which you would join them up. To be absolutely clear, the first and second values in each of the \$n\$ rows are respectively an \$x\$- and a \$y\$-coordinate.
* If it would be far more natural to take something other than a 2D matrix in your language or it's impossible to take one, you can use something else. Should this happen, please clearly state what you're doing.
* \$x\$-coordinates or \$y\$-coordinates may be negative, zero or positive.
* The polygon formed by joining up the points in the given order may be convex or concave.
* There's no need to consider [degenerate polygons](https://cs.stackexchange.com/questions/12521/what-are-degenerate-polygons).
* No input polygon will be self-intersecting, thank goodness.
**Output:** two numbers of any numeric type, respectively representing the \$x\$-coordinate and \$y\$-coordinate of a point within the polygon.
* No, your numbers needn't be integers.
* Your output needn't be consistent for any single input. You're allowed to generate an output in any valid way that shortens your code.
* Corners and edge points are forbidden. Sorry.
### Example 1
Input:
```
0 0
3 0
3 4
```
Possible output: `1 1`
### Example 2
Input:
```
-3 -1
0 1
-1 -1
-1 0
```
Possible output: `-0.31416 0.42`
# Remarks
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so fewest bytes wins.
* The [random](/questions/tagged/random "show questions tagged 'random'") tag is here only to be on the safe side. I expect that not every answer will use randomness.
* [Standard rules](https://codegolf.meta.stackexchange.com/questions/2419/default-for-code-golf-program-function-or-snippet/), [I/O rules](https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods) and [loophole rules](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) apply.
* If possible, link an online demo of your code.
* Please explain your code.
  
[Answer]
# [Python 3.8](https://docs.python.org/3.8/), ~~116~~ 110 bytes
```
lambda p:[x:=min(p)[0]+.1,sum(sorted(b+(d-b)*(x-a)/(c-a)for(a,b),(c,d)in zip(p,p[-1:]+p)if(a<x)^(c<x))[:2])/2]
```
[Try it online!](https://tio.run/##JY/bboMwDIbveQqrvbHbQDnsYkLrXgSYFE5aJEitJNXoqj47M0xy7Pj//VkJP8L3zRbv7NbxWq@TntteA5fVUl5nY5GpSptzkil/n9HfXBh6bM/Yxy2dcIk1XbCTPN4catWSwk71ZCz8GkZWXMVZ2ZyZzIj6Y6Ev7CRTVeYNXfJmNTPLSvAPH0WyAiZjBxBahMSH3tgyAjiCG3QvMt@DtPY@e7jCrBmNDWpnEs@TCUgkPos5GR9we8KpMmFwuDHUnPJ94AjshARt/c/gRHBCjPLTDd4cHA9PfkH8Wdune9X2QGsKKRT7eYviAuJM7tlW/iP9Aw "Python 3.8 – Try It Online")
**Input**: A list of points, each is a tuple of 2 integers.  
**Output**: A point as a list of 2 numbers.
### Approach
Draw a vertical line through the polygon. Select the first 2 points where the line intersects with the polygon edges. Any point between those 2 points must be inside the polygon.
[![How to pick an inside point](https://i.stack.imgur.com/nTYsgm.png)](https://i.stack.imgur.com/nTYsgm.png)
Note that the line should be chosen such that it doesn't intersect any polygon vertex.
### Code explanation
The x-coordinate of the line is selected as the minimum `x` of all vertices, plus a small amount (`0.1` is used in this case):
```
x:=min(p)[0]+.1
```
This ensures that the line intersects the polygon, and that it doesn't pass through any vertex (since vertices all have integer coordinates).
For each edge through vertices \$(a,b)\$ and \$(c,d)\$, the line intersects the edge if \$a<x<c\$ or \$a>x>c\$. Golfed using xor trick:
```
if (a<x)^(b<x)
```
The y-coordinate of each intersection is calculated using the following formula:
$$\frac{y-b}{x-a}=\frac{d-b}{c-a}$$
or `b+(d-b)*(x-a)/(c-a)`
The y-coordinate of the final point is calculated as the average of the smallest 2 y-coordinates.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 11 bytes
Mathematica has a built-in for pointing ion cannons. In fact, as far as I know, it should support self-intersecting roofs. Takes input as a polygon.
```
RandomPoint
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE7872Yb8z8oMS8lPzcgPzOv5H9AEZB0cIsOyM@pTM/Pi66uNtRRMKzVUag20VEwgdJgvrGOglFtbWzsfwA "Wolfram Language (Mathematica) – Try It Online")
By the way, `RandomPoint@Polygon@#&` is 5 bytes of Sledgehammer: `⡘⠼⡃⡖⣳`.
[Answer]
# [Perl 5](https://www.perl.org/), 191 bytes
```
sub{sub c{($_[0]+$_[1])/2}map{$x{$_->[0]}=0}@_;$x=c sort
keys%x;for(0..$#_){($t,$y)=@{$_[$_]};($d=$_[$_-1][0]-$t)&&($t=($x-$t)/$d,$t*(1-$t)>0&&push@y,$y+$t*($_[$_-1][1]-$y))}@{[$x,c
sort@y]}}
```
It's deterministic and O(n).
Choose an \$x\$-coordinate \$P\_x\$ (`$x`) halfway between the smallest two unique input \$x\$ coordinates. Test each polygon side to see if that line segment intersects the \$x=P\_x\$ vertical line. If it does, add the \$y\$-coordinate of that intersection point to `@y`. Finally, let \$P\_y\$ be halfway between the two smallest values in `@y`, and the output is \$(P\_x,P\_y)\$: since you cross exactly one edge to get here from the \$y=-\infty\$ end of the \$x=P\_x\$ line, the point must be inside the polygon.
[Try it online!](https://tio.run/##PVDLbsMgELzzFSt3a0GDE9y0J4uI/3ARSh23TVs/ZIhky@Lb3XVS5cDAzO6M2O3r4fd1aSbAfug@h2OjF395n@lANXN0pbIbwtyK3XNsjv2M44wuO5AetYrGFTjqCnw3BPZTT/5xLD66gavtFh@coIQgcRLakKlEZ2PB8aSv7yy3FJJhEGlKbZrjuJIdniSGJ56v5KDStL/4LzNRymaV79acrJMQ0cwljrJi6w/MZGNcCkbjmFD74EEDZwBlqaSystz/44u18ipne0lZksorZvmN0a2sZaJgNArwW5SAGfrh3Ab47s4tT2Qi7zvLDtygE0JC8tYmENnyBw "Perl 5 – Try It Online")
[Answer]
# Java 10, 378 bytes
```
import java.awt.geom.*;X->Y->{var p=new Path2D.Double();p.moveTo(X[0],Y[0]);int l=X.length,f=1,i=1;for(;i<l;)p.lineTo(X[i],Y[i++]);p.closePath();var r=p.getBounds();double x=0,y=0;for(;f>0;)for(x=r.getX()+Math.random()*r.getWidth(),y=r.getY()+Math.random()*r.getHeight(),i=f=0;i<l-1;)f=!p.contains(x,y)|new Line2D.Double(X[i],Y[i++],X[i],Y[i]).contains(x,y)?1:f;return x+","+y;}
```
Having builtins is usually an advantage, right?.. :/ I'll see if a manual approach is shorter later on.
Input-coordinates as two loose arrays for `x` and `y` respectively, output as a comma-delimited String of the random `x,y`-coordinate.
[Try it online.](https://tio.run/##jZFNi9swEIbv@RXTPVlrWWtveqpWKZSl9NCFwhaaEHzQxnKi1JaMPc7GpP7t6ShJaQs5LBgjjeZ95uPd6p1OtsXPo60b3yJs6S70K4q18bW4lXB3B/H9FNADbgy8DGiSle8dTlaV7jp40tYdJgAdarSrs7xHW4mydyu03onPl8ODdbjM@VtSnrG1bj2bQQkKjvNktkhmh51uoVHOvMI3jZv7R/Ho@5fKREw2ovY7891H82Wa8wX9mCQSVGouKuPWuOFWZbxUmSx9G0n7UEnWiMq6s8gGkY3jPKBWle9MqEDgULJVDe0CP9HMRUex4lQV9irlg0rPwHKWShZOe9WG5HnE4idCiFa7wtcRuz2Ff9giYEl3ui6uZ30xdr1BSrOqpALUbJIRXb2j3rxD2ncX7fnAfoVVfKUZ/q7in1H4n3PO/pd9zD6UsjXYtw728Q2/iQc5HuWEPGwIQh5erNx5W0BNuuhsxzIHzYLVAM9Dh6YWvkfR0BNWLiqFbppqiEJTJxcPKZ/y6ciuxFP@fmRMvh2VTEmTZPRd4VE8vPD0whwn4/E3)
**Explanation:**
```
import java.awt.geom.*;      // Required import for Path2D and Line2D
X->Y->{                      // Method with two int-arrays as parameters and String return-type
  var p=new Path2D.Double(); //  Create a Path2D
  p.moveTo(X[0],Y[0]);       //  Start at the first input-coordinate
  int l=X.length,            //  Store the amount of points in `l`
      f=1,                   //  Flag integer, starting at 1
  i=1;for(;i<l;)             //  Loop `i` in the range [1, l):
    p.lineTo(X[i],Y[i++]);   //   And draw a line to the `i`'th x,y-coordinate of the input
  p.closePath();             //  Close the path, so we now have our polygon
  var r=s.getBounds();       //  Create a Rectangle that encapsulates this polygon
  double x=0,y=0;            //  Create the random x,y-coordinate
  for(;f>0;)                 //  Loop as long as the flag is still 1:
    for(x=r.getX()+Math.random()*r.getWidth(),y=r.getY()+Math.random()*r.getHeight(),
                             //   Get a random x,y-coordinate within the Rectangle
        i=f=0;               //   (Re)set both the flag and `i` to 0
        i<l-1;)              //   Inner loop `i` in the range [0, l-1):
      f=!p.contains(x,y)     //    If the Path2D-polygon does NOT contain this random x,y-coordinate
        |                    //    Or:
         new Line2D.Double(  //    Create a Line2D
          X[i],Y[i++],       //    from the `i`'th x,y-coordinate of the input
          X[i],Y[i])         //    to the `i+1`'th x,y-coordinate of the input
         .contains(x,y)?     //    And if this line does contain the random x,y-coordinate:
          1                  //     Change the flag to 1
        :                    //    Else:
          f;                 //     Keep the flag the same
  return x+","+y;}           //  And finally return our random x,y-coordinate as String
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 19 bytes
```
`xx,Xr]yy&G4$TF#ZQ~
```
The input is a vector with *x* coordinates, then a vector with *y* coordinates. The ouput is *x*, then *y*. Running time is random, but finite with probability 1.
[Try it online!](https://tio.run/##y00syfn/P6GiQieiKLayUs3dRCXETTkqsO7//2hdYwUDBV1DIIrligbSIJaCQSwA "MATL – Try It Online")
### How it works
The program randomly generates points with a bidimensional Gaussian distribution until one of them happens to be inside the polygon. This distribution spans the full plane, so the code eventually finds a solution.
```
`       % Do...while
  xx    %   Delete twice. In the first iterarion this takes the two inputs
        %   (implicitly) and deletes them. In subsequent iterations this
        %   deletes the previous x, y candidate coordinates, which turned out
        %   not to be a solution
  ,     %   Do twice
    Xr  %     Generate a random number with a standard Gaussian distribution.
        %     Note that his covers the whole plane, although points close to
        %     the origin have greater a probability density
  ]     %   End. The stack contains two numbers representing x, y coordinates
        %   of a potential solution
  yy    %   Duplicate top two elements in the stack
  &G    %   Push the two inputs
  4$    %   Specify four inputs for the next function
  TF#   %   Specify the first of two possible outputs for the next function
  ZQ    %   Inpolygon function: takes four inputs, where the first and second
        %   define x, y coordinates of a point, and the third and fourth define
        %   the x, y coordinates of the polygon vertices. The (first) output is
        %   true if the point is strictly in the polygon, and false if not
  ~     %   Negate
        % End (implicit). A new iteration starts if the top of the stack is
        % true, meaning that the tested x, y values were not a solution
        % Display (implicit)
```
[Answer]
# [Erlang (escript)](http://erlang.org/doc/man/escript.html), 174 bytes
```
f(P)->X=hd(lists:min(P))+0.1,[X,lists:sum(lists:sublist(lists:sort([B+(D-B)*(X-A)/(C-A)||{[A,B],[C,D]}<-lists:zip(P,[lists:last(P)|lists:droplast(P)]),(A<X)xor(C<X)]),2))/2].
```
[Try it online!](https://tio.run/##ZU7LboNADLznKzjaiU0g7SlKIwH5AI5I1h5IQ9qVeGmhapXSb6emBLVSffA8NGO5cGVev3DRPTvb9uNqvEKKfMyeXi9Q2q7v9pWt1cJN4IckGc1m91bBws4TWVTjepB4AyeOcQ0ZR7iFRPcwfEpEsSFJ6GS@Djznb7aFlGQWZa53UhxmdXFNe3cMEkSHDD8aB4mi6h3idmf8scr1PTHo8XHl6dhm/@5sX8AVRALyAkOePPziozGIpKm6BKT/FdYMh1NYyz/I4eJMLPjb98dv "Erlang (escript) – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), 89 bytes
```
l=input()
(B,b),(A,a),(C,c)=min(zip(l[1:]+l,l,l[2:]+l))
print.2+B,b+(a+c-b*2)/(A+C-B*2)/5
```
[Try it online!](https://tio.run/##VYzNCoMwEITvPkXxtGk2VtP2InhQHyPkoEEwkKahpPTn5dOspYey7PLNsDPhFderl@mxWrfsmnZ5LqYsy@Q668M9AitgwJkh9DjlO6Jh3cV6eNsATjWt5g7zKEnEWBFu1sdK8hziMHEj5r1kB@j5KAaic6J2BXVVY95cefyjUyZdKBAkRLP59PslMn7uxhTUHw "Python 2 – Try It Online")
Here's the strategy for picking the point:
* Take the vertex \$p\$ with the smallest \$x\$-coordinate. If there's a tie, any is fine.
* Consider the two edges leading from \$p\$. To obtain a direction that's in between them, add them as vectors.
* Travel from \$p\$ in this direction far enough to go +0.2 units in the \$x\$ direction, and pick the point you arrive at.
Because \$p\$ is among the leftmost points of the polygon, any direction that's in between the two edges leading from it points inside the polygon. Because we only travel 0.2 units in the \$x\$ direction and all vertices lie on integer points, we can't have exited the polygon after going less than 0.5.
]