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
...
qth query

Each query consists of integer coordinates of end points of s1 and s2 in the following format:

xp0 yp0 xp1 yp1 xp2 yp2 xp3 yp3

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 ≤ xpi, ypi ≤ 10000

p0 &ne; p1 and
p2 &ne; 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



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

Submission status: Accepted

Solution code:
import math

class Vector:
    def __init__(self,x,y):
        self.x = x
        self.y = y
        
    def __add__(self,other):
        return Vector(self.x+other.x,self.y+other.y)
    
    def __sub__(self,other):
        return Vector(self.x-other.x,self.y-other.y)
    
    def __mul__(self,scalar):
        return Vector(self.x*scalar,self.y*scalar)
    def __rmul__(self, scalar):
        return Vector(self.x*scalar,self.y*scalar)
   
    def __repr__(self):
        return str([self.x,self.y])
        
    def norm_2(self):
        return dot(self,self)
    
    def norm(self):
        return math.sqrt(self.norm_2())
    
def v_sum(v1,v2):
    return Vector(v1.x+v2.x,v1.y+v2.y) 
def scalar_multi(k,v):
    return Vector(k*v.x,k*v.y)
def v_diff(v1,v2):
    return v_sum(v1,scalar_multi(-1,v2))
    
def dot(vector1,vector2):
    return vector1.x*vector2.x+vector1.y*vector2.y

def cross(vector1,vector2):
    return vector1.x*vector2.y-vector1.y*vector2.x
    
    
def in_seg(p,s,t):
    '''
    whether point p is in the area of segment(s,t)
    '''
    x = p-s
    d = t-s
    if 0<=dot(x,d)/d.norm_2()<=1:
        return True
    else:
        return False
    
def is_crossed(p,q,s,t):
    a = q-p
    b = t-s
    v = s-p
    w = t-p
    x = p-s
    y = q-s
    if cross(a,v)*cross(a,w)<=0 and cross(b,x)*cross(b,y)<=0:
        if cross(a,v) == cross(a,w) == cross(b,x) == cross(b,y) == 0: 
            #if segments are on the same line, you must check whether an end point is in the other segment at least
            if 0<=dot(a,v)<=a.norm_2() or 0<=dot(a,w)<=a.norm_2() or 0<=dot(b,x)<=b.norm_2() or 0<=dot(b,y)<=b.norm_2():
                return True
            else:
                return False
        else:    
            return True
    else:
        return False
    
def point_line_dist(p,s,t):
    x = p-s
    d = t-s
    return abs(cross(x,d))/d.norm()

def calc(p1,p2,p3,p4):
    min_dists = []
    if in_seg(p1,p3,p4):
        min_dists.append(point_line_dist(p1,p3,p4))
    if in_seg(p2,p3,p4):
        min_dists.append(point_line_dist(p2,p3,p4))
    if in_seg(p3,p1,p2):
        min_dists.append(point_line_dist(p3,p1,p2))
    if in_seg(p4,p1,p2):
        min_dists.append(point_line_dist(p4,p1,p2))
    
    min_dists.append((p1-p3).norm())
    min_dists.append((p1-p4).norm())
    min_dists.append((p2-p3).norm())
    min_dists.append((p2-p4).norm())
    
    if is_crossed(p1,p2,p3,p4):
        min_dists.append(0)
    
    return min(min_dists)

q = int(input())

for i in range(q):
    x1,y1,x2,y2,x3,y3,x4,y4 = map(float,input().split())
    p1 = Vector(x1,y1)
    p2 = Vector(x2,y2)
    p3 = Vector(x3,y3)
    p4 = Vector(x4,y4)
    print(calc(p1,p2,p3,p4))

Submission status: Accepted

Solution code:
EPS = 10**(-9)
def is_equal(a,b):
    return abs(a-b) < EPS

def norm(v,i=2):
    import math
    ret = 0
    n = len(v)
    for j in range(n):
        ret += abs(v[j])**i
    return math.pow(ret,1/i)

class Vector(list):
    """
    ベクトルクラス
    対応演算子
    +  : ベクトル和 
    -  : ベクトル差
    *  : スカラー倍、または内積
    /  : スカラー除法
    ** : 外積
    += : ベクトル和
    -= : ベクトル差
    *= : スカラー倍
    /= : スカラー除法

    メソッド
    self.norm(i) : L{i}ノルムを計算
    """
    def __add__(self,other):
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i) + other.__getitem__(i)
        return self.__class__(ret)
    
    def __radd__(self,other):
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = other.__getitem__(i) + super().__getitem__(i)
        return self.__class__(ret)
    
    def __iadd__(self, other):
        n = len(self)
        for i in range(n):
            self[i] += other.__getitem__(i)
        return self

    def __sub__(self,others):
        n = len(self) 
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i) - others.__getitem__(i)
        return self.__class__(ret)

    def __iadd__(self, other):
        n = len(self)
        for i in range(n):
            self[i] -= other.__getitem__(i)
        return self

    def __rsub__(self,others):
        n = len(self) 
        ret = [0]*n
        for i in range(n):
            ret[i] = others.__getitem__(i) - super().__getitem__(i)
        return self.__class__(ret)
    
    def __mul__(self,other):
        n = len(self)
        if isinstance(other,list):
            ret = 0
            for i in range(n):
                ret += super().__getitem__(i)*other.__getitem__(i)
            return ret
        else:
            ret = [0]*n
            for i in range(n):
                ret[i] = super().__getitem__(i)*other
            return self.__class__(ret)

    def __rmul__(self,other):
        n = len(self)
        if isinstance(other,list):
            ret = 0
            for i in range(n):
                ret += super().__getitem__(i)*other.__getitem__(i)
            return ret
        else:
            ret = [0]*n
            for i in range(n):
                ret[i] = super().__getitem__(i)*other
            return self.__class__(ret)
    
    
    def __truediv__(self,other):
        """
        ベクトルのスカラー除法
        Vector/scalar
        """
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i)/other
        return self.__class__(ret)
    
    def norm(self,i):
        """
        L{i}ノルム
        self.norm(i)
        """
        return norm(self,i)
    
    def __pow__(self,other):
        """
        外積
        self**other
        """
        n = len(self)
        ret = [0]*3
        x = self[:]
        y = other[:]
        if n == 2:
            x.append(0)
            y.append(0)
        if n == 2 or n == 3:
            for i in range(3):
                ret[0],ret[1],ret[2] = x[1]*y[2]-x[2]*y[1],x[2]*y[0]-x[0]*y[2],x[0]*y[1]-x[1]*y[0]
            ret = Vector(ret)
            if n == 2:
                return ret
            else:
                return ret

class Segment:
    """
    線分クラス
    """
    def __init__(self,v1,v2):
        self.v1 = v1
        self.v2 = v2
    
    def length(self):
        return norm(self.v1-self.v2)

    def get_unit_vec(self):
        #方向単位ベクトル
        dist = norm(self.v2-self.v1)
        if dist != 0:
            return (self.v2-self.v1)/dist
        else:
            return False
    
    def projection(self,vector):
        #射影点(線分を直線と見たときの)
        unit_vec = self.get_unit_vec()
        t = unit_vec*(vector-self.v1)
        return self.v1 + t*unit_vec
    
    def is_vertical(self,other):
        #線分の直交判定
        return is_equal(0,self.get_unit_vec()*other.get_unit_vec())
    
    def is_horizontal(self,other):
        #線分の平行判定
        return is_equal(0,self.get_unit_vec()**other.get_unit_vec())
    
    def reflection(self,vector):
        #反射点(線分を直線と見たときの)
        projection = self.projection(vector)
        v = projection - vector
        return projection + vector
    
    def include(self,vector):
        #線分が点を含むか否か
        proj = self.projection(vector)
        if not is_equal(norm(proj-vector),0):
            return False
        else:
            n = len(self.v1)
            f = True
            for i in range(n):
                f &= ((self.v1[i] <= vector[i] <= self.v2[i]) or (self.v2[i] <= vector[i] <=self.v1[i]))
            return f
    
    def distance(self,other):
        #点と線分の距離
        if isinstance(other,Vector):
            proj = self.projection(other)
            if self.include(proj):
                return norm(proj-other)
            else:
                ret = []
                ret.append(norm(self.v1-other))
                ret.append(norm(self.v2-other))
                return min(ret)

    def ccw(self,vector):
        """
        線分に対して点が反時計回りの位置にある(1)か時計回りの位置にある(-1)か線分上にある(0)か
        """
        direction = self.v2 - self.v1
        v = vector - self.v1
        if self.include(vector):
            return 0
        else:
            cross = direction**v
            if cross[2] <= 0:
                return 1
            else:
                return -1
    
    def intersect(self,segment):
        """
        線分の交差判定
        """
        ccw12 = self.ccw(segment.v1)
        ccw13 = self.ccw(segment.v2)
        ccw20 = segment.ccw(self.v1)
        ccw21 = segment.ccw(self.v2)
        
        if ccw12*ccw13*ccw20*ccw21 == 0:
            return True
        else:
            if ccw12*ccw13 < 0 and ccw20*ccw21 < 0:
                return True
            else:
                return False

class Line(Segment):
    """
    直線クラス
    """
    #直線上に点が存在するか否か
    def include(self,vector):
        proj = self.projection(vector)
        return is_equal(norm(proj-vector),0)

q = int(input())
ps =[[[0] for _ in range(4)] for _ in range(q)]
for i in range(q):
    tmp = list(map(int,input().split()))
    for j in range(4):
        ps[i][j] = Vector(tmp[2*j:2*(j+1)])

for i in range(q):
    ans = []
    p0,p1,p2,p3 = ps[i]
    S1 = Segment(p0,p1)
    S2 = Segment(p2,p3)
    if S1.intersect(S2):
        ans.append(0)
    else:
        ans.append(S1.distance(p2))
        ans.append(S1.distance(p3))
        ans.append(S2.distance(p0))
        ans.append(S2.distance(p1))
    
    print(min(ans))

Submission status: Accepted

Solution code:
import math

class Point:
    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):
        return Point(self.x * other, self.y * other)
    def __floordiv__(self, other):
        return Point(self.x / other, self.y / other)
    def __repr__(self):
        return str(self.x) + ' ' + str(self.y)

class Vector(Point):
    pass

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

class Segment(Line):
    pass

def points_to_vector(p1, p2):
    x = p1.x - p2.x
    y = p1.y - p2.y
    return Vector(x, y)

def vector(p):
    return Vector(p.x, p.y)

def dot(v1, v2):
    return v1.x * v2.x + v1.y * v2.y

def cross(v1, v2):
    return v1.x * v2.y - v1.y * v2.x

def norm(v):
    return v.x**2 + v.y**2

def distance(v):
    return math.sqrt(norm(v))

def project(s, p):
    base = points_to_vector(s.p1, s.p2)
    hypo = points_to_vector(p, s.p1)
    r = dot(hypo, base) / norm(base)
    return s.p1 + base * r

def reflect(s, p):
    return p + (project(s, p) -p) * 2

def get_distance(s1, s2):
    if intersect_s(s1, s2):
        return 0
    d1 = get_distance_sp(s1, s2.p1)
    d2 = get_distance_sp(s1, s2.p2)
    d3 = get_distance_sp(s2, s1.p1)
    d4 = get_distance_sp(s2, s1.p2)
    return min(d1, min(d2, min(d3, d4)))

def get_distance_pp(p1, p2):
    return distance(p1 - p2)

def get_distance_lp(l, p):
    return abs(cross(l.p2 - l.p1, p - l.p1) / distance(l.p2 - l.p1))

def get_distance_sp(s, p):
    if dot(s.p2 - s.p1, p - s.p1) < 0:
        return distance(p - s.p1)
    elif dot(s.p1 - s.p2, p - s.p2) < 0:
        return distance(p - s.p2)
    else:
        return get_distance_lp(s, p)

def ccw(p0, p1, p2):
    EPS = 1e-10
    COUNTER_CLOCKWISE = 1
    CLOCKWISE = -1
    ONLINE_BACK = 2
    ONLINE_FRONT = -2
    ON_SEGMENT = 0
    v1 = p1 - p0
    v2 = p2 - p0
    if cross(v1, v2) > EPS:
        return COUNTER_CLOCKWISE
    elif cross(v1, v2) < -EPS:
        return CLOCKWISE
    elif dot(v1, v2) < -EPS:
        return ONLINE_BACK
    elif norm(v1) < norm(v2):
        return ONLINE_FRONT
    else:
        return ON_SEGMENT

def intersect_p(p1, p2, p3, p4):
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0

def intersect_s(s1, s2):
    return intersect_p(s1.p1, s1.p2, s2.p1, s2.p2)


import sys
# sys.stdin = open('input.txt')

q = int(input())
for i in range(q):
    temp = list(map(int, input().split()))
    points = []
    for j in range(0, 8, 2):
        points.append(Point(temp[j], temp[j+1]))
    s1 = Segment(points[0], points[1])
    s2 = Segment(points[2], points[3])
    print(get_distance(s1, s2))

Submission status: Accepted

Solution code:
from functools import singledispatch
import math

EPS = 1e-10

COUNTER_CLOCKWISE = 1
CLOCKWISE = -1
ONLINE_BACK = 2
ONLINE_FRONT = -2
ON_SEGMENT = 0

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

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

    def __add__(self, point):
        # + 演算子での挙動を指定
        return Point(self.x+point.x, self.y+point.y)

    def __sub__(self, point):
        # - 演算子での挙動を指定
        return Point(self.x-point.x, self.y-point.y)

    def __mul__(self, a):
        # * 演算子での挙動を指定
        return Point(a*self.x, a*self.y)

    def __truediv__(self, a):
        # / 演算子での挙動を指定
        return Point(self.x/a, self.y/a)

    def __abs__(self):
        # abs関数での挙動を指定
        return math.sqrt(self.norm())

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

    def __eq__(self, point):
        # == 演算子での挙動を指定
        return abs(self.x-point.x) < EPS and abs(self.y-point.y) <EPS

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 isOrthogonal(a, b):
    return dot(a, b) == 0

def isParallel(a, b):
    return cross(a, b) == 0

def project(s, p):
    #s: Segment(), p: Point()
    base = s.p2 - s.p1
    r = dot(p-s.p1, base)/base.norm()
    return s.p1+base*r

def reflect(s, p):
    return p+(project(s, p)-p)*2

@singledispatch
def get_distance(a, b):
    return abs(a-b)

def get_distance_lp(l, p):
    return abs(cross(l.p2-l.p1, p-l.p1)/abs(l.p2-l.p1))

def get_distance_sp(s, p):
    if dot(s.p2-s.p1, p-s.p1) < 0:
        return abs(p-s.p1)
    if dot(s.p1-s.p2, p-s.p2) < 0:
        return abs(p-s.p2)
    return get_distance_lp(s, p)
    
@get_distance.register(Segment)
def _(s1, s2):
    if intersect(s1, s2):
        return 0
    return min([get_distance_sp(s1, s2.p1), get_distance_sp(s1, s2.p2),
                get_distance_sp(s2, s1.p1), get_distance_sp(s2, s1.p2)])

def ccw(p0, p1, p2):
    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

@singledispatch
def intersect(p1, p2, p3, p4):
    return (ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0
            and ccw(p3, p4, p1)*ccw(p3, p4, p2) <= 0)

@intersect.register(Segment)
def _(s1, s2):
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2)


if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    q = int(input())
    for _ in range(q):
        x0, y0, x1, y1, x2, y2, x3, y3 = map(int, input().split())
        p0 = Point(x0, y0)
        p1 = Point(x1, y1)
        p2 = Point(x2, y2)
        p3 = Point(x3, y3)
        s1 = Segment(p0, p1)
        s2 = Segment(p2, p3)
        print(get_distance(s1, s2))

Submission status: Accepted

Solution code:
from math import pi, cos, sin, atan2
EPS = 10**(-9)

def eq(value1, value2):
    return abs(value1-value2) <= EPS

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.arg = atan2(y, x) # -PI ~ PI
    
    def __str__(self):
        return "{0:.8f} {1:.8f}".format(self.x, self.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, scal):
        return Point(self.x*scal, self.y*scal)
    
    def __truediv__(self, scal):
        return Point(self.x/scal, self.y/scal)
    
    def __eq__(self, other):
        return eq(self.x, other.x) and eq(self.y, other.y)

    # 原点からの距離
    def __abs__(self):
        return (self.x**2+self.y**2)**0.5
    
# 原点を中心にrad角だけ回転した点
def Rotation(vec: Point, rad):
    return Point(vec.x*cos(rad)-vec.y*sin(rad), vec.x*sin(rad)+vec.y*cos(rad))


class Circle():
    def __init__(self, p, r):
        self.p = p
        self.r = r


class Line():
    # 点a, bを通る
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.arg = (a-b).arg % pi
    
    def __str__(self):
        return "[({0}, {1}) - ({2}, {3})]".format(self.a.x, self.a.y, self.b.x, self.b.y)

    # pointを通って平行
    def par(self, point):
        return Line(point, point+(self.a-self.b))

    # pointを通って垂直
    def tan(self, point):
        return Line(point, point + Rotation(self.a-self.b, pi/2))


class Segment(Line):
    def __init__(self, a, b):
        super().__init__(a, b)


# 符号付き面積
def cross(vec1: Point, vec2: Point):
    return vec1.x*vec2.y - vec1.y*vec2.x

# 内積
def dot(vec1: Point, vec2: Point):
    return vec1.x*vec2.x + vec1.y*vec2.y

# 点a->b->cの回転方向
def ccw(a, b, c):
    if cross(b-a, c-a) > EPS: return +1 # COUNTER_CLOCKWISE
    if cross(b-a, c-a) < -EPS: return -1 # CLOCKWISE
    if dot(c-a, b-a) < -EPS: return +2 # c -> a -> b
    if abs(b-a) < abs(c-a): return -2 # a -> b -> c
    return 0 # a -> c -> b


# pのlへの射影
def projection(l, p):
    t = dot(l.b-l.a, p-l.a) / abs(l.a-l.b)**2
    return l.a + (l.b-l.a)*t

# pのlによる反射
def reflection(l, p):
    return p + (projection(l, p) - p)*2

def isPararell(l1, l2):
    return eq(cross(l1.a-l1.b, l2.a-l2.b), 0)

def isVertical(l1, l2):
    return eq(dot(l1.a-l1.b, l2.a-l2.b), 0)


def isIntersect_lp(l, p):
    return abs(ccw(l.a, l.b, p)) != 1

def isIntersect_ll(l1, l2):
    return not isPararell(l1, l2) or isIntersect_lp(l1, l2.a)

def isIntersect_sp(s, p):
    return ccw(s.a, s.b, p) == 0

def isIntersect_ss(s1, s2):
    return ccw(s1.a, s1.b, s2.a)*ccw(s1.a, s1.b, s2.b) <= 0 and ccw(s2.a, s2.b, s1.a)*ccw(s2.a, s2.b, s1.b) <= 0

def isIntersect_ls(l, s):
    return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS

def isIntersect_cp(c, p):
    return abs(abs(c.p - p) - c.r) < EPS

def isIntersect_cl(c, l):
    return distance_lp(l, c.p) <= c.r + EPS

def isIntersect_cs(c, s):
    pass

def isIntersect_cc(c1, c2):
    pass


def distance_pp(p1, p2):
    return abs(p1-p2)

def distance_lp(l, p):
    return abs(projection(l,p)-p)

def distance_ll(l1, l2):
    return 0 if isIntersect_ll(l1, l2) else distance_lp(l1, l2.a)

def distance_sp(s, p):
    r = projection(s, p)
    if isIntersect_sp(s, r): return abs(r-p)
    return min(abs(s.a-p), abs(s.b-p))

def distance_ss(s1, s2):
    if isIntersect_ss(s1, s2): return 0
    return min([distance_sp(s1, s2.a), distance_sp(s1, s2.b), distance_sp(s2, s1.a), distance_sp(s2, s1.b)])

def distance_ls(l, s):
    if isIntersect_ls(l, s): return 0
    return min(distance_lp(l, s.a), distance_lp(l, s.b))


def crosspoint_ll(l1, l2):
    A = cross(l1.b - l1.a, l2.b - l2.a)
    B = cross(l1.b - l1.a, l1.b - l2.a)
    if eq(abs(A), 0) and eq(abs(B), 0): return l2.a
    return l2.a + (l2.b - l2.a) * B / A

def crosspoint_ss(s1, s2):
    return crosspoint_ll(s1, s2)

def crosspoint_lc(l, c):
    if eq(distance_lp(l, c.p), c.r): return [c.p]
    p = projection(l, c.p)
    e = (l.b - l.a) / abs(l.b-l.a)
    dis = (c.r**2-abs(p-c.p)**2)**0.5
    return [p + e*dis, p - e*dis]

def crosspoint_sc(s, c):
    pass

def crosspoint_cc(c1, c2):
    d = abs(c1.p-c2.p)
    if not abs(c1.r-c2.r) <= d <= c1.r+c2.r:
        return []
    mid_p = (c2.p * (c1.r**2-c2.r**2+d**2) + c1.p * (c2.r**2-c1.r**2+d**2)) / (2*d**2)
    tanvec = Rotation(c1.p-c2.p, pi/2)
    return crosspoint_lc(Line(mid_p, mid_p+tanvec), c1)


# pからのcの接点
def tangent_cp(c, p):
    return crosspoint_cc(c, Circle(p, (abs(p-c.p)**2 - c.r**2)**0.5))





import sys
input = sys.stdin.readline

def verify_1A():
    p1x, p1y, p2x, p2y = map(int, input().split())
    l = Line(Point(p1x, p1y), Point(p2x, p2y))
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        print(projection(l, p))

def verify_1B():
    p1x, p1y, p2x, p2y = map(int, input().split())
    l = Line(Point(p1x, p1y), Point(p2x, p2y))
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        print(reflection(l, p))

def verify_1C():
    p1x, p1y, p2x, p2y = map(int, input().split())
    p1 = Point(p1x, p1y); p2 = Point(p2x, p2y)
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        result = ccw(p1, p2, p)
        if result == 1:
            print("COUNTER_CLOCKWISE")
        elif result == -1:
            print("CLOCKWISE")
        elif result == 2:
            print("ONLINE_BACK")
        elif result == -2:
            print("ONLINE_FRONT")
        else:
            print("ON_SEGMENT")

def verify_2A():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        l1 = Line(Point(p0x, p0y), Point(p1x, p1y))
        l2 = Line(Point(p2x, p2y), Point(p3x, p3y))
        if isPararell(l1, l2):
            print(2)
        elif isVertical(l1, l2):
            print(1)
        else:
            print(0)

def verify_2B():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        s1 = Segment(Point(p0x, p0y), Point(p1x, p1y))
        s2 = Segment(Point(p2x, p2y), Point(p3x, p3y))
        if isIntersect_ss(s1, s2):
            print(1)
        else:
            print(0)


def verify_2C():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        s1 = Segment(Point(p0x, p0y), Point(p1x, p1y))
        s2 = Segment(Point(p2x, p2y), Point(p3x, p3y))
        print(crosspoint_ss(s1, s2))  

def verify_2D():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        s1 = Segment(Point(p0x, p0y), Point(p1x, p1y))
        s2 = Segment(Point(p2x, p2y), Point(p3x, p3y))
        print("{:.8f}".format(distance_ss(s1, s2)))

verify_2D()

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
import math

def cross(a,b): #外積
  return a.real*b.imag-a.imag*b.real

def dot(a,b): #内積
  return a.real*b.real+a.imag*b.imag

def norm2(a,b): #大きさの2乗
  return (b.real-a.real)**2+(b.imag-a.imag)**2

def is_intersect(p0,p1,p2,p3): #交差しているのかを判定
  ta=cross(p1-p0,p2-p0)
  tb=cross(p1-p0,p3-p0)
  tc=cross(p3-p2,p0-p2)
  td=cross(p3-p2,p1-p2)

  if ta*tb<0 and tc*td<0:
    return True
  else:
    return False

def distance_option(p0,p1,p2):
  nn=norm2(p0,p1)
  #print(dot(p1-p0,p2-p0),nn)
  if 0<=dot(p1-p0,p2-p0)<=nn:
    return abs(cross(p1-p0,p2-p0))/math.sqrt(nn)
  else:
    return math.sqrt(min(norm2(p0,p2),norm2(p1,p2)))

def distance(p0,p1,p2,p3):
  if is_intersect(p0,p1,p2,p3):
    return 0
  else:
    #print(distance_option(p0,p1,p2),distance_option(p0,p1,p3),distance_option(p2,p3,p0),distance_option(p2,p3,p1))
    return min(distance_option(p0,p1,p2),distance_option(p0,p1,p3),distance_option(p2,p3,p0),distance_option(p2,p3,p1))

q=int(input())

for _ in [0]*q:
  x_y=map(int,input().split())
  p0,p1,p2,p3=[x+y*1j for x,y in zip(*[x_y]*2)]
  print("{:.10f}".format(distance(p0,p1,p2,p3)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

EPS = 0.0000000001

COUNTER_CLOCKWISE = 1
CLOCKWISE = -1
ONLINE_BACK = 2
ONLINE_FRONT = -2
ON_SEGMENT = 0

class Point:
    
    global EPS
    
    def __init__(self, x = 0, y = 0):
        self.x = x
        self.y = y
        
        
    def __add__(a, b):
        s = a.x + b.x
        t = a.y + b.y
        return Point(s, t)
        
    def __sub__(a, b):
        s = a.x - b.x
        t = a.y - b.y
        return Point(s, t)
            
    def __mul__(self, a):
        s = a * self.x
        t = a * self.y
        return Point(s, t)
        
    def __truediv__(self, a):
        s = self.x / a
        t = self.y / a
        return Point(s, t)
            
            
            
            
    def norm(self):
        return self.x * self.x + self.y * self.y
        
    def abs(self):
        return self.norm() ** 0.5
            
    
            
            
    def __eq__(self, other):
        return abs(self.x - other.y) < self.EPS and abs(self.y - other.y) < self.EPS
            
            
            
    def dot(self, b):
        return self.x * b.x + self.y * b.y
        
    def cross(self, b):
        return self.x * b.y - self.y * b.x
    
    
class Segment:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2

def project(s, p):
    base = s.p2 - s.p1
    hypo = p - s.p1
    r = hypo.dot(base) / base.norm()
    return s.p1 + base * r

def reflecton(s, p):
    return p + (project(s,p) - p) * 2


def getDistance(a, b):
    return (a-b).abs()

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

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


def getDistanceSS(s1, s2):
    if intersectS(s1, s2):
        return 0
    return min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2), getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2))



def ccw(p0, p1, p2):
    a = p1-p0
    b = p2-p0
    
    if a.cross(b) > 0:
        return COUNTER_CLOCKWISE
    elif a.cross(b) <0:
        return CLOCKWISE
    elif a.dot(b) < 0:
        return ONLINE_BACK
    elif a.abs() < b.abs():
        return ONLINE_FRONT
    else:
        return ON_SEGMENT

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

def intersectS(s1, s2):
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2)




n = int(input())
for i in range(n):
    
    nums=list(map(int,input().split()))
    s1 = Segment(Point(nums[0], nums[1]), Point(nums[2], nums[3]))
    s2 = Segment(Point(nums[4], nums[5]), Point(nums[6], nums[7]))
    print(getDistanceSS(s1, s2))