Problem:
Distance For given two segments s1 and s2 , print the distance between them.  s1 is formed by end points p0 and p1 , and s2 is formed by end points p2 and p3 . Input The entire input looks like:  q (the number of queries)
1st query
2nd query
... q th query Each query consists of integer coordinates of end points of s1 and s2 in the following format:  x p0  y p0  x p1  y p1  x p2  y p2  x p3  y p3  Output For each query, print the distance. The output values should be in a decimal fraction with an error less than 0.00000001. Constraints  1 ≤ q ≤ 1000  -10000 ≤ x p i , y p i ≤ 10000   p0 ≠ p1 and p2 ≠ p3 .  Sample Input 3
0 0 1 0 0 1 1 1
0 0 1 0 2 1 1 2
-1 0 1 0 0 1 0 -1 Sample Output 1.0000000000
1.4142135624
0.0000000000

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())




def sgn(a):
    if a < -eps: return -1
    if a >  eps: return  1
    return 0

class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y
        pass

    def tolist(self):
        return [self.x,self.y]

    def __add__(self,p):
        return Point(self.x+p.x, self.y+p.y)
    def __iadd__(self,p):
        return self + p

    def __sub__(self,p):
        return Point(self.x - p.x, self.y - p.y)
    def __isub__(self,p):
        return self - p

    def __truediv__(self,n):
        return Point(self.x/n, self.y/n)
    def __itruediv__(self,n):
        return self / n

    def __mul__(self,n):
        return Point(self.x*n, self.y*n)
    def __imul__(self,n):
        return self * n

    def __lt__(self,other):
        tmp = sgn(self.x - other.x)
        if tmp != 0:
            return tmp < 0
        else:
            return sgn(self.y - other.y) < 0

    def __eq__(self,other):
        return sgn(self.x - other.x) == 0 and sgn(self.y - other.y) == 0

    def abs(self):
        return math.sqrt(self.x**2+self.y**2)

    def dot(self,p):
        return self.x * p.x + self.y*p.y

    def det(self,p):
        return self.x * p.y - self.y*p.x

    def arg(self,p):
        return math.atan2(y,x)


def iSP(a,b,c):
    tmp = sgn((b-a).det(c-a))
    if tmp > 0:   return 1   
    elif tmp < 0: return -1  
    else: 
        if sgn((b-a).dot(c-a)) < 0: return -2 
        if sgn((a-b).dot(c-b)) < 0: return  2 
        return 0 


def isToleranceLine(a,b,c,d):
    if sgn((b-a).det(c-d)) != 0: return 1 
    else:
        if sgn((b-a).det(c-a)) != 0: return 0 
        else: return -1 


def isToleranceSegline(a,b,c,d):
    return sgn(iSP(a,b,c)*iSP(a,b,d))<=0 and sgn(iSP(c,d,a)*iSP(c,d,b)) <= 0


def Intersection(a,b,c,d):
    tmp1 = (b-a)*((c-a).det(d-c))
    tmp2 = (b-a).det(d-c)
    return a+(tmp1/tmp2)


def DistanceLineToPoint(a,b,c):
    return abs(((c-a).det(b-a))/((b-a).abs()))


def DistanceSeglineToPoint(a,b,c):
    if sgn((b-a).dot(c-a)) < 0: 
        return (c-a).abs()
    if sgn((a-b).dot(c-b)) < 0: 
        return (c-b).abs()
    return DistanceLineToPoint(a,b,c)


def Vfoot(a,b,c):
    d = c + Point((b-a).y,-(b-a).x)
    return Intersection(a,b,c,d)


def PolygonArea(Plist):
    Plist = ConvexHull(Plist)
    L = len(Plist)
    S = 0
    for i in range(L):
        tmpS = (Plist[i-1].det(Plist[i]))/2
        S += tmpS
    return S


def PolygonG(Plist):
    Plist = ConvexHull(Plist)
    L = len(Plist)
    S = 0
    G = Point(0,0)
    for i in range(L):
        tmpS = (Plist[i-1].det(Plist[i]))/2
        S += tmpS
        G += (Plist[i-1]+Plist[i])/3*tmpS
    return G/S


def ConvexHull(Plist):
    Plist.sort()
    L = len(Plist)
    qu = deque([])
    quL = 0
    for p in Plist:
        while quL >= 2 and iSP(qu[quL-2],qu[quL-1],p) == 1:
            qu.pop()
            quL -= 1
        qu.append(p)
        quL += 1

    qd = deque([])
    qdL = 0
    for p in Plist:
        while qdL >= 2 and iSP(qd[qdL-2],qd[qdL-1],p) == -1:
            qd.pop()
            qdL -= 1
        qd.append(p)
        qdL += 1

    qd.pop()
    qu.popleft()
    hidari = list(qd) + list(reversed(qu)) 
    return hidari

N = int(input())
for _ in range(N):
    x0,y0,x1,y1,x2,y2,x3,y3 = inpl()
    p0 = Point(x0,y0)
    p1 = Point(x1,y1)
    p2 = Point(x2,y2)
    p3 = Point(x3,y3)
    if isToleranceSegline(p0,p1,p2,p3):
        print(0)
    else:
        print(min(DistanceSeglineToPoint(p0,p1,p2),\
                  DistanceSeglineToPoint(p0,p1,p3),\
                  DistanceSeglineToPoint(p2,p3,p0),\
                  DistanceSeglineToPoint(p2,p3,p1)))

Solution (Python):
import math


class Vector2():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, v):
        return Vector2(self.x+v.x, self.y+v.y)

    def __sub__(self, v):
        return Vector2(self.x-v.x, self.y-v.y)

    def __mul__(self, v):
        return Vector2(self.x*v, self.y*v)

    def __truediv__(self, v):
        return Vector2(self.x/v, self.y/v)

    def __abs__(self):
        return math.sqrt(float(self.x*self.x+self.y*self.y))

    def dot(self, v):
        return self.x*v.x+self.y*v.y

    def cross(self, v):
        return self.x*v.y-self.y*v.x

    def norm(self):
        d = abs(self)
        return Vector2(self.x/d, self.y/d)


def distanceLP(v1, v2, p):
    '''
    v1 -> v2の直線とpとの距離
    '''
    return abs((v2-v1).cross(p-v1))/abs(v2-v1)


def distanceSP(v1, v2, p):
    '''
    v1 -> v2の線分とpとの距離
    '''
    if (v2-v1).dot(p-v1) < 0.0:
        return abs(p-v1)
    if (v1-v2).dot(p-v2) < 0.0:
        return abs(p-v2)
    return distanceLP(v1, v2, p)


def intersect(p1, p2, p3, p4):
    '''
    p1p2とp3p4の交差判定
    '''
    t1 = (p1.x-p2.x)*(p3.y-p1.y)+(p1.y-p2.y)*(p1.x-p3.x)
    t2 = (p1.x-p2.x)*(p4.y-p1.y)+(p1.y-p2.y)*(p1.x-p4.x)
    t3 = (p3.x-p4.x)*(p1.y-p3.y)+(p3.y-p4.y)*(p3.x-p1.x)
    t4 = (p3.x-p4.x)*(p2.y-p3.y)+(p3.y-p4.y)*(p3.x-p2.x)
    return (t1*t2) < 0.0 and (t3*t4) < 0.0


def distance(a1, a2, b1, b2):
    '''
    線分a1a2とb1b2の距離
    '''
    if intersect(a1, a2, b1, b2):
        return 0.0
    return min([
        min([distanceSP(a1, a2, b1), distanceSP(a1, a2, b2)]),
        min([distanceSP(b1, b2, a1), distanceSP(b1, b2, a2)])
    ])


q = int(input())
for i in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, input().split())
    p0 = Vector2(x0, y0)
    p1 = Vector2(x1, y1)
    p2 = Vector2(x2, y2)
    p3 = Vector2(x3, y3)
    s1 = p1-p0
    s2 = p3-p2
    print(f"{distance(p0, p1, p2, p3):.10f}")

Solution (Python):
import math


def dot(ux, uy, vx, vy):
    return ux*vx + uy*vy


def cross(ux, uy, vx, vy):
    return ux*vy - uy*vx


def dist_to_segment(x, y, ax, ay, bx, by):
    if dot(x - ax, y - ay, bx - ax, by - ay) < 0:
        return math.hypot(x - ax, y - ay)
    if dot(x - bx, y - by, ax - bx, ay - by) < 0:
        return math.hypot(x - bx, y - by)
    c = abs(cross(bx - ax, by - ay, x - ax, y - ay))
    return c / math.hypot(bx - ax, by - ay)


q = int(input())

for _ in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, input().split())

    c1 = cross(x1 - x0, y1 - y0, x2 - x0, y2 - y0)
    c2 = cross(x1 - x0, y1 - y0, x3 - x0, y3 - y0)
    c3 = cross(x3 - x2, y3 - y2, x0 - x2, y0 - y2)
    c4 = cross(x3 - x2, y3 - y2, x1 - x2, y1 - y2)

    if c1*c2 < 0 and c3*c4 < 0:
        d = 0.0
    else:
        d = dist_to_segment(x2, y2, x0, y0, x1, y1)
        d = min(d, dist_to_segment(x3, y3, x0, y0, x1, y1))
        d = min(d, dist_to_segment(x0, y0, x2, y2, x3, y3))
        d = min(d, dist_to_segment(x1, y1, x2, y2, x3, y3))

    print('{:.10f}'.format(d))

Solution (Python):



from math import sqrt


class Segment:
    def __init__(self, p0, p1):
        self.end_points = (p0, p1)

    def another(self, p):
        if p == self.end_points[0]:
            return self.end_points[1]
        else:
            return self.end_points[0]

    def distance(self, other):
        def _distance(p, seg):
            p0 = seg._closest_point(p)
            p1 = seg.another(p0)
            x, y = p
            x0, y0 = p0
            x1, y1 = p1
            vp = (x-x0, y-y0)
            vseg = (x1-x0, y1-y0)
            if dot(vp, vseg) <= 0:
                return length(vp)
            else:
                x, y = vp
                return length(projection(vp, orthogonal(vseg)))

        if self.intersect(other):
            return 0.0

        dists = []
        for p0 in self.end_points:
            dists.append(_distance(p0, other))
        for p1 in other.end_points:
            dists.append(_distance(p1, self))

        return min(dists)

    def intersect(self, other):
        p0, p1 = self.end_points
        p2, p3 = other.end_points

        if convex(p0, p2, p1, p3):
            return True
        else:
            if (p0 in other or p1 in other
                    or p2 in self or p3 in self):
                return True

        return False

    def _closest_point(self, p):
        p0, p1 = self.end_points
        x, y = p
        x0, y0 = p0
        x1, y1 = p1
        if length((x0-x, y0-y)) < length((x1-x, y1-y)):
            return p0
        else:
            return p1

    def __contains__(self, p):
        p0, p1 = self.end_points
        x0, y0 = p0
        x1, y1 = p1
        x, y = p
        v = (x1-x0, y1-y0)
        v0 = (x-x0, y-y0)
        v1 = (x-x1, y-y1)
        if dot(orthogonal(v0), v1) == 0:
            if abs(length(v0) + length(v1) - length(v)) < 1e-10:
                return True
        return False


def dot(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    return x1 * x2 + y1 * y2


def orthogonal(v):
    x, y = v
    return -y, x


def length(v):
    x, y = v
    return sqrt(x**2 + y**2)


def projection(p, v):
    x, y = v
    r = dot(p, v) / dot(v, v)
    return (x*r, y*r)


def convex(p0, p1, p2, p3):
    ret = []
    for pa, pb, pc in zip([p0, p1, p2, p3],
                          [p1, p2, p3, p0],
                          [p2, p3, p0, p1]):
        xa, ya = pa
        xb, yb = pb
        xc, yc = pc
        v1 = (xb - xa, yb - ya)
        v2 = (xc - xb, yc - yb)
        ret.append(dot(orthogonal(v1), v2))

    return all([d > 0 for d in ret]) or all([d < 0 for d in ret])


def run():
    q = int(input())

    for _ in range(q):
        x0, y0, x1, y1, x2, y2, x3, y3 = [int(i) for i in input().split()]

        s0 = Segment((x0, y0), (x1, y1))
        s1 = Segment((x2, y2), (x3, y3))

        print("{:.10f}".format(s0.distance(s1)))


if __name__ == '__main__':
    run()

Solution (Python):
import math
from typing import Union


class Point(object):
    __slots__ = ['x', 'y']

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __mul__(self, other: Union[int, float]):
        return Point(self.x * other, self.y * other)

    def norm(self):
        return pow(self.x, 2) + pow(self.y, 2)

    def abs(self):
        return math.sqrt(self.norm())

    def __repr__(self):
        return f"({self.x},{self.y})"


class Vector(Point):
    __slots__ = ['x', 'y', 'pt1', 'pt2']

    def __init__(self, pt1: Point, pt2: Point):
        super().__init__(pt2.x - pt1.x, pt2.y - pt1.y)
        self.pt1 = pt1
        self.pt2 = pt2

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def __repr__(self):
        return f"{self.pt1},{self.pt2}"


class Segment(Vector):
    __slots__ = ['x', 'y', 'pt1', 'pt2']

    def __init__(self, pt1: Point, pt2: Point):
        super().__init__(pt1, pt2)

    def projection(self, pt: Point)-> Point:
        t = self.dot(Vector(self.pt1, pt)) / self.norm()
        return self.pt1 + self * t

    def reflection(self, pt: Point) -> Point:
        return self.projection(pt) * 2 - pt

    def is_intersected_with(self, other) -> bool:
        if (self.point_geometry(other.pt1) * self.point_geometry(other.pt2)) <= 0\
                and other.point_geometry(self.pt1) * other.point_geometry(self.pt2) <= 0:
            return True
        else:
            return False

    def point_geometry(self, pt: Point) -> int:
        """
        [-2:"Online Back", -1:"Counter Clockwise", 0:"On Segment", 1:"Clockwise",  2:"Online Front"]
        """
        vec_pt1_to_pt = Vector(self.pt1, pt)
        cross = self.cross(vec_pt1_to_pt)
        if cross > 0:
            return -1   
        elif cross < 0:
            return 1    
        else:           
            dot = self.dot(vec_pt1_to_pt)
            if dot < 0:
                return -2    
            else:       
                if self.abs() < vec_pt1_to_pt.abs():
                    return 2    
                else:
                    return 0    

    def cross_point(self, other) -> Point:
        d1 = abs(self.cross(Vector(self.pt1, other.pt1)))       
        d2 = abs(self.cross(Vector(self.pt1, other.pt2)))       
        t = d1 / (d1 + d2)
        return other.pt1 + other * t

    def distance_to_point(self, pt: Point) -> Union[int, float]:
        vec_pt1_to_pt = Vector(self.pt1, pt)
        if self.dot(vec_pt1_to_pt) <= 0:
            return vec_pt1_to_pt.abs()
        vec_pt2_to_pt = Vector(self.pt2, pt)
        if Vector.dot(self * -1, vec_pt2_to_pt) <= 0:
            return vec_pt2_to_pt.abs()
        return (self.projection(pt) - pt).abs()

    def segment_distance(self, other) -> Union[int, float]:
        if self.is_intersected_with(other):
            return 0.0
        else:
            return min(
                self.distance_to_point(other.pt1),
                self.distance_to_point(other.pt2),
                other.distance_to_point(self.pt1),
                other.distance_to_point(self.pt2)
            )

    def __repr__(self):
        return f"{self.pt1},{self.pt2}"


def main():
    num_query = int(input())
    for i in range(num_query):
        p0_x, p0_y, p1_x, p1_y, p2_x, p2_y, p3_x, p3_y = map(int, input().split())
        seg_1 = Segment(Point(p0_x, p0_y), Point(p1_x, p1_y))
        seg_2 = Segment(Point(p2_x, p2_y), Point(p3_x, p3_y))

        print(f'{seg_1.segment_distance(seg_2):.10f}')
    return


main()

Solution (Python):
from math import sqrt

def cross(p0, p1, p2):
  x0, y0 = p0
  x1, y1 = p1
  x2, y2 = p2
  x1 -=x0
  x2 -=x0
  y1 -=y0
  y2 -=y0
  return x1*y2 - x2*y1

def dot(p0, p1, p2):
  x0, y0 = p0
  x1, y1 = p1
  x2, y2 = p2
  x1 -=x0
  x2 -=x0
  y1 -=y0
  y2 -=y0
  return x1*x2 + y1*y2

def dist2(p0, p1):
  x0, y0 = p0
  x1, y1 = p1
  return (x1-x0)**2 + (y1 - y0)**2

def collision_ll(s0, s1,t0,t1):
  return cross(s0, s1,t0)*cross(s0,s1,t1)<0 and cross(t0, t1,s0) * cross(t0,t1,s1) < 0

def dist_lp(S,E,P):
  dd = dist2(S,E)
  if 0 <= dot(S,E,P) <= dd:
    return abs(cross(S,E,P))/sqrt(dd)
  return sqrt(min(dist2(S,P), dist2(E,P)))

def dist_ll(s0, s1, t0, t1):
  if collision_ll(s0,s1,t0,t1):
    return 0
  return min(
    dist_lp(s0, s1, t0),
    dist_lp(s0, s1, t1),
    dist_lp(t0, t1, s0),
    dist_lp(t0, t1, s1)
    )

n = int(input())
for i in range(n):
  x0,y0,x1,y1,X0,Y0,X1,Y1 = map(int,input().split())
  print("%.010f"%dist_ll((x0,y0), (x1,y1), (X0,Y0),(X1,Y1)))

Solution (Python):
import math

EPS = 1e-10

def equals(a, b):
    return abs(a - b) < EPS


class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, p):
        return Point(self.x + p.x, self.y + p.y)

    def __sub__(self, p):
        return Point(self.x - p.x, self.y - p.y)

    def __mul__(self, a):
        return Point(self.x * a, self.y * a)

    def __rmul__(self, a):
        return self * a

    def __truediv__(self, a):
        return Point(self.x / a, self.y / a)

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return math.sqrt(self.norm())

    def __lt__(self, p):
        if self.x != p.x:
            return self. x < p.x
        else:
            return self.y < p.y

    def __eq__(self, p):
        return equals(self.x, p.x) and equals(self.y, p.y)


class Segment:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2


def dot(a, b):
    return a.x * b.x + a.y * b.y


def cross(a, b):
    return a.x * b.y - a.y * b.x


def ccw(p0, p1, p2):
    COUNTER_CLOCKWISE = 1
    CLOCKWISE = -1
    ONLINE_BACK = 2
    ONLINE_FRONT = -2
    ON_SEGMENT = 0
    a = p1 - p0
    b = p2 - p0
    if cross(a, b) > EPS:
        return COUNTER_CLOCKWISE
    if cross(a, b) < -EPS:
        return CLOCKWISE
    if dot(a, b) < -EPS:
        return ONLINE_BACK
    if a.norm() < b.norm():
        return ONLINE_FRONT
    return ON_SEGMENT


def intersect(s1, s2):
    p1 = s1.p1
    p2 = s1.p2
    p3 = s2.p1
    p4 = s2.p2
    return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and
            ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0)


def getDistanceLP(l, p):
    v = l.p2 - l.p1
    return abs(cross(v, p - l.p1) / v.abs())


def getDistanceSP(s, p):
    if dot(s.p2 - s.p1, p - s.p1) < 0:
        v = p - s.p1
        return v.abs()
    if dot(s.p1 - s.p2, p - s.p2) < 0:
        v = p - s.p2
        return v.abs()
    return getDistanceLP(s, p)


def getDistance(s1, s2):
    if intersect(s1, s2):
        return 0
    return min(
        getDistanceSP(s1, s2.p1),
        getDistanceSP(s1, s2.p2),
        getDistanceSP(s2, s1.p1),
        getDistanceSP(s2, s1.p2)
    )


if __name__ == '__main__':
    q = int(input())
    ans = []
    for i in range(q):
        x0, y0, x1, y1, x2, y2, x3, y3 = [int(v) for v in input().split()]
        s1 = Segment(Point(x0, y0), Point(x1, y1))
        s2 = Segment(Point(x2, y2), Point(x3, y3))
        ans.append(getDistance(s1, s2))

    for v in ans:
        print('{0:.10f}'.format(v))

Solution (Python):


import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def in_sec(a, b, c):
    return min(a, b) <= c <= max(a, b)
def dist(xp, yp, xq, yq):
    return math.sqrt((xq - xp) ** 2 + (yp - yq) ** 2)
def min_d(x, y, xp, yp, xq, yq):
    vx, vy = [xp - xq, yp - yq]
    vx1, vy1 = [x - xp, y - yp]
    vx2, vy2 = [x - xq, y - yq]
    if (vx1 * vx + vy1 * vy) * (vx2 * vx + vy2 * vy) < 0:
        a, b, c = [yq - yp, xp - xq, xp * (yp - yq) + yp * (xq - xp)]
        return abs(a * x + b * y + c) / math.sqrt(a ** 2 + b ** 2)
    return min(dist(x, y, xp, yp), dist(x, y, xq, yq))

q = input()

for loop in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(float, raw_input().split())
    
    a1, b1, c1 = [y1 - y0, x0 - x1, x0 * (y1 - y0) - y0 * (x1 - x0)]
    a2, b2, c2 = [y3 - y2, x2 - x3, x2 * (y3 - y2) - y2 * (x3 - x2)]
    det = a1 * b2 - b1 * a2
    if det == 0:
        dx, dy = [x2 - x0, y2 - y0]
        if dx * a1 + dy * b1 == 0 and \
            not(max(x0, x1) < min(x2, x3) or max(x2, x3) < min(x0, x1) \
            or max(y0, y1) < min(y2, y3) or max(y2, y3) < min(y0, y1)):
            print 0
            continue
    else:
        xdet = c1 * b2 - c2 * b1
        ydet = c2 * a1 - c1 * a2
        if in_sec(det * x0, det * x1, xdet) and in_sec(det * y0, det * y1, ydet) \
            and in_sec(det * x2, det * x3, xdet) and in_sec(det * y2, det * y3, ydet):
            print 0
            continue

    ans = min(min_d(x0, y0, x2, y2, x3, y3), min_d(x1, y1, x2, y2, x3, y3), 
        min_d(x2, y2, x0, y0, x1, y1), min_d(x3, y3, x0, y0, x1, y1))
    print "%.10f" % ans