J, 40 39 34 bytes
3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-
An anonymous dyadic function, taking a point, p, as one of its arguments, and a list of points, P, as the other argument (it doesn't matter which argument is which), and returning 0 or 1, if p is outside or inside the convex hull of P, respectively.
The point p, and the points in P, are taken as complex numbers.
Example
is_inside =: 3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-
0.5j0.5 is_inside 0j0 0j1 1j0 1j1
1
1.5j0.5 is_inside 0j0 0j1 1j0 1j1
0
or...
Python 2, function, 121 103, full program, 162
Python 3, 149 bytes
import sys,cmath as C
p,q,*P=[complex(*eval(l.replace(*";,")))for l in sys.stdin]
A=[C.phase((r-p)/(q-p+(q==p)))for r in P]
print(max(A)-min(A)>C.pi)
Takes input, in the same format as the original post, through STDIN, and prints a boolean value indicating whether p is in the convex hull of P
Explanation
The program tests whether the difference between the maximum and minimum (signed) angles between any point r in P, p, and a fixed arbitrary point q in P (we just use the first point in P), is less than 180°.
In other words, it tests whether all the points in P are contained in an angle of 180° or less, around p.
p is in the convex hull of P if and only if this condition is false.
At the cost of a few more bytes, we can use a similar method that doesn't require us to explicitly calculate angles:
Note that the above condition is equivalent to saying that p is outside the convex hull of P if and only if there exists a line l through p, such that all the points in P are on the same side of l.
If such a line exists, then there's also such a line that is incident to one (or more) of the points in P (we can rotate l until it touches one of the points in P.)
To (tentatively) find this line, we start by letting l be the line through p and the first point in P.
We then iterate over the rest of the points in P; if one of the points is to the left of l (we assume some directionality throughout, left or right doesn't really matter,) we replace l with the line passing through p and that point, and continue.
After we iterated over all of P, if (and only if) p is outside the convex hull, then all the points in P should be to the right of (or on) l.
We check that using a second pass over the points in P.
Python 2, 172 bytes
import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=reduce(lambda*x:x[C(*x)],P)
print any(C(l,q)for q in P)
Alternatively, to do the same thing in a single pass, let to-the-left-of be a realtion between any two points, q and r, in P, such that q is to the left of r if q is to the left of the line passing through p and r.
Note that to-the-left-of is an order relation on P if and only if all the points in P are on the same side of some line passing through p, that is, if p is outside the convex hull of P.
The procedure described above finds the minimum point in P w.r.t. this order, i.e., the "leftmost" point in P.
Instead of performing two passes, we can find the maximum (i.e., the "rightmost" point), as well as the minimum, points in P w.r.t. the same order in a single pass, and verify that the minimum is to the left of the maximum, i.e., effectively, that to-the-left-of is transitive.
This would work well if p is outside the convex hull of P, in which case to-the-left-of is actually an order relation, but may break when p is inside the convex hull (for example, try to figure out what will happen if we ran this algorithm where the points in P are the vertices of a regular pentagon, running counter-clockwise, and p is its center.)
To accommodate, we slightly alter the algorithm:
We select a point q in P, and bisect P along the line passing through p and q (i.e., we partition P around q w.r.t. to-the-left-of.)
We now have a "left part" and a "right part" of P, each contained in a halfplane, so that to-the-left-of is an order relation on each; we find the minimum of the left part, and the maximum of the right part, and compare them as described above.
Of course, we don't have to physically bisect P, we can simply classify each point in P as we look for the minimum and maximum, in a single pass.
Python 2, 194 bytes
import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=r=P[0]
for q in P:
if C(P[0],q):l=q*C(l,q)or l
elif C(q,r):r=q
print C(l,r)
3What is an "ad hoc data structure"? – DavidC – 2015-12-11T18:25:08.047
"elementary functions/operators" is much too vague. – xnor – 2015-12-11T18:27:18.137
@DavidCarraher: something like a Polygon, or a Triangle, or a Segment (anything that exists only to solve geometric problems). – Alexandre Halm – 2015-12-11T18:28:57.253
@quintopia: any builtin that solves the convex hull problem is forbidden (what would be the point). – Alexandre Halm – 2015-12-11T18:38:15.060
@xnor: tried to clarify. – Alexandre Halm – 2015-12-11T18:38:32.820
2@AlexandreHalm Your edit helped a lot. I think "elementary" isn't the right word. I thought it would eliminate general-purpose built-ins like
sortorround. I think it's clearer to just say nothing specifically made for geometry is allowed. What, though, about a function to add two lists as vectors? Or a function to find the argument (angle) of a complex number? – xnor – 2015-12-11T18:42:33.910@xnor: good question. What would you suggest? – Alexandre Halm – 2015-12-11T19:03:38.863
@AlexandreHalm I think it's too fuzzy to delineate between generic geometric operations and generic list/complex operations. Maybe just ban things specifically having to do with complex hull, polygons, and geometric inclusion? That might still be too vague. Another solution is to just allow anything and let Mathematica do what it wants. – xnor – 2015-12-11T19:09:24.440
Are the input points guaranteed to be "on" the hull, or could some of them be meaningless since they're "inside" as well? (Or, phrased another way, do the input points form a convex polygon) – AdmBorkBork – 2015-12-11T19:36:52.783
1
This is why the Diamonds request people please use the Sandbox before posting new challenges.
– cat – 2015-12-11T20:15:19.057@TimmyD: the points are random (i.e. they don't necessarily form a convex polygon). It wouldn't be fun otherwise – Alexandre Halm – 2015-12-12T07:31:53.220
@AlexandreHalm Is it ok to call a linear programming algorithm (eg.
boot::simplexin R), or does linear algebra count as geometric? – han – 2015-12-13T10:56:04.397@han: linear algebra and complex numbers are indeed a bit tricky. Let's say both are fine (I'll edit the question to clarify this). Just no "pure" geometry. – Alexandre Halm – 2015-12-13T11:01:49.273