#define T 20000
#define N double
N sqrt(N);N D(a,b){N x=a%T-b%T,y=a/T-b/T;return sqrt(x*x+y*y);}F,L,P;f(a,b,c,d){F=L=-1;for(P=0;++P<T*T;L=(D(a,P)+D(P,b)-D(a,b)<0.001&&D(c,P)+D(P,d)-D(c,d)<0.001)?(F=(F<0?P:F)),P:L);a=(F+L)/2;}
Try it online!
Very slow. Input format is endpoints packed into ints as coordinate multiplied
by 100 (to an integer) and 10000 added to it (to a natural). Y coordinate is
multiplied by an additional 20000 to pack it next to X coordinate. No collision
is signaled by the point (-100.01,-100).
Thus the X coordinate of a point A is ((A%20000)-10000)/100.0 and the Y
coordinate is ((A/20000)-10000)/100.0.
Rationale
Thanks to the question providing no time limit and specifying a desired
precision accurately, a non-optimal solution can be used to reduce code size.
Thus instead of actually computing the collision points, then doing some
additional logic if the lines are coincident, this checks every single point of
the given precision and sees if it is a collision.
This collision check is much shorter (code-wise) than the collision computation.
In particular to check if a point collides with a line segment just check if the
distance to each endpoint adds up to the length of the segment. If a point
collides with both line segments individually, then it is a point where the line
segments intersect.
Using this strategy the code finds the endpoints of the collision and returns
their midpoint. Initially they are set to -1, so if there is no collision it
returns -1 (-1+-1/2) which when translated back is a number just out of range.
If there's only one collision point, it is stored in both endpoints, so it is
itself returned (x+x/2). Finally, if there is an overlap the overlap must be a
line, returning the average of the line's endpoints will yield the midpoint.
Algorithm
As such, the algorithm in pseudo-code would be:
collision (AB,CD):
start and end = -1
for each point P:
if P is in both line segments AB and CD
if start = -1, start = P
end = P
return (start+end)/2
is P in line segment AB:
return distance(A,P) + distance(P,B) = distance(A,B)
Description
The annotated source is thus:
#define T 20000 // We use 20000 a lot
#define N double // We use double a lot
N sqrt(N); // We need to prototype sqrt or it will be assumed to be int(int)
N D(a,b){ // D defines the distance function
N x=a%T-b%T, // x is delta x
y=a/T-b/T; // y is delta y
return sqrt(x*x+y*y);} // standard distance formula: sqrt(dx^2+dy^2)
F, // F is the first point of collision
L, // L is the last point of collision
P; // P is the current test point
f(a,b,c,d){ // f takes the 4 segment end-points
F=L=-1; // Initialize both collision points to -1 (invalid)
for(P=0;++P<T*T; // Loop P over each point
L= // Set the last collision point based on a ternary
(D(a,P)+D(P,b)-D(a,b) // We have to use an epsilon check due to floating point rounding errors
<0.001 // This accuracy is definitionally good enough
&& // The previous check was for collision with AB
D(c,P)+D(P,d)-D(c,d) // now we have to check for collision with CD
<0.001)? // if both collide - we have a collision point!
(F=(F<0?P:F)), // if the first collision point isn't set, this is it
P // set the last collision point no matter what
: // they don't both collide, ignore this point
L); // the expression is assigned to L, so keep L the same
a= // return by assigning to the first argument
(F+L)/2;} // the average of the first and last points
// Luckily the packing of the points fits with enough space so we
// don't have to worry about averaging each coordinate separately
