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:
#! /usr/bin/env python3

from typing import List, Tuple
from math import sqrt

EPS = 1e-10


def float_equal(x: float, y: float) -> bool:
    return abs(x - y) < EPS


class Point:

    def __init__(self, x: float=0.0, y: float=0.0) -> None:
        self.x = x
        self.y = y

    def __repr__(self) -> str:
        return "Point({}, {})".format(self.x, self.y)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Point):
            # print("NotImplemented in Point")
            return NotImplemented
        return float_equal(self.x, other.x) and \
            float_equal(self.y, other.y)

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

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

    def __mul__(self, k: float) -> 'Point':
        return Point(self.x * k, self.y * k)

    def __rmul__(self, k: float) -> 'Point':
        return self * k

    def __truediv__(self, k: float) -> 'Point':
        return Point(self.x / k, self.y / k)

    def __lt__(self, other: 'Point') -> bool:
        return self.y < other.y \
            if abs(self.x - other.x) < EPS \
            else self.x < other.x

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

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

    def dot(self, other: 'Point') -> float:
        return self.x * other.x + self.y * other.y

    def cross(self, other: 'Point') -> float:
        return self.x * other.y - self.y * other.x

    def is_orthogonal(self, other: 'Point') -> bool:
        return float_equal(self.dot(other), 0.0)

    def is_parallel(self, other: 'Point') -> bool:
        return float_equal(self.cross(other), 0.0)

    def distance(self, other: 'Point') -> float:
        return (self - other).abs()

    def in_side_of(self, seg: 'Segment') -> bool:
        return seg.vector().dot(
            Segment(seg.p1, self).vector()) >= 0

    def in_width_of(self, seg: 'Segment') -> bool:
        return \
            self.in_side_of(seg) and \
            self.in_side_of(seg.reverse())

    def distance_to_segment(self, seg: 'Segment') -> float:
        if self.in_width_of(seg):
            return self.distance(seg.projection(self))
        else:
            return min(self.distance(seg.p1),
                       self.distance(seg.p2))


Vector = Point


class Segment:

    def __init__(self, p1: Point = None, p2: Point = None) -> None:
        self.p1: Point = Point() if p1 is None else p1
        self.p2: Point = Point() if p2 is None else p2

    def __repr__(self) -> str:
        return "Segment({}, {})".format(self.p1, self.p2)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Segment):
            # print("NotImplemented in Segment")
            return NotImplemented
        return self.p1 == other.p1 and self.p2 == other.p2

    def vector(self) -> Vector:
        return self.p2 - self.p1

    def reverse(self) -> 'Segment':
        return Segment(self.p2, self.p1)

    def is_orthogonal(self, other: 'Segment') -> bool:
        return self.vector().is_orthogonal(other.vector())

    def is_parallel(self, other: 'Segment') -> bool:
        return self.vector().is_parallel(other.vector())

    def projection(self, p: Point) -> Point:
        v = self.vector()
        vp = p - self.p1
        return v.dot(vp) / v.norm() * v + self.p1

    def reflection(self, p: Point) -> Point:
        x = self.projection(p)
        return p + 2 * (x - p)

    def intersect_ratio(self, other: 'Segment') -> Tuple[float, float]:
        a = self.vector()
        b = other.vector()
        c = self.p1 - other.p1
        s = b.cross(c) / a.cross(b)
        t = a.cross(c) / a.cross(b)
        return s, t

    def intersects(self, other: 'Segment') -> bool:
        s, t = self.intersect_ratio(other)
        return (0 <= s <= 1) and (0 <= t <= 1)

    def intersection(self, other: 'Segment') -> Point:
        s, _ = self.intersect_ratio(other)
        return self.p1 + s * self.vector()

    def distance_with_segment(self, other: 'Segment') -> float:
        if not self.is_parallel(other) and \
                self.intersects(other):
            return 0
        else:
            return min(
                self.p1.distance_to_segment(other),
                self.p2.distance_to_segment(other),
                other.p1.distance_to_segment(self),
                other.p2.distance_to_segment(self))


Line = Segment


class Circle:

    def __init__(self, c: Point=None, r: float=0.0) -> None:
        self.c: Point = Point() if c is None else c
        self.r: float = r

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Circle):
            return NotImplemented
        return self.c == other.c and self.r == other.r

    def __repr__(self) -> str:
        return "Circle({}, {})".format(self.c, self.r)
        
def main() -> None:
    n = int(input())

    for _ in range(n):
        x1, y1, x2, y2, x3, y3, x4, y4 = [int(x) for x in input().split()]
        s1 = Segment(Point(x1, y1), Point(x2, y2))
        s2 = Segment(Point(x3, y3), Point(x4, y4))
        print(s1.distance_with_segment(s2))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

from typing import List, Tuple
from math import sqrt

EPS = 1e-10


def float_equal(x: float, y: float) -> bool:
    return abs(x - y) < EPS


class Point:

    def __init__(self, x: float=0.0, y: float=0.0) -> None:
        self.x = x
        self.y = y

    def __repr__(self) -> str:
        return "Point({}, {})".format(self.x, self.y)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Point):
            # print("NotImplemented in Point")
            return NotImplemented
        return float_equal(self.x, other.x) and \
            float_equal(self.y, other.y)

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

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

    def __mul__(self, k: float) -> 'Point':
        return Point(self.x * k, self.y * k)

    def __rmul__(self, k: float) -> 'Point':
        return self * k

    def __truediv__(self, k: float) -> 'Point':
        return Point(self.x / k, self.y / k)

    def __lt__(self, other: 'Point') -> bool:
        return self.y < other.y \
            if abs(self.x - other.x) < EPS \
            else self.x < other.x

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

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

    def dot(self, other: 'Point') -> float:
        return self.x * other.x + self.y * other.y

    def cross(self, other: 'Point') -> float:
        return self.x * other.y - self.y * other.x

    def is_orthogonal(self, other: 'Point') -> bool:
        return float_equal(self.dot(other), 0.0)

    def is_parallel(self, other: 'Point') -> bool:
        return float_equal(self.cross(other), 0.0)

    def distance(self, other: 'Point') -> float:
        return (self - other).abs()

    def in_side_of(self, seg: 'Segment') -> bool:
        return seg.vector().dot(
            Segment(seg.p1, self).vector()) >= 0

    def in_width_of(self, seg: 'Segment') -> bool:
        return \
            self.in_side_of(seg) and \
            self.in_side_of(seg.reverse())

    def distance_to_line(self, seg: 'Segment') -> float:
        return \
            abs((self - seg.p1).cross(seg.vector())) / \
            seg.length()

    def distance_to_segment(self, seg: 'Segment') -> float:
        if not self.in_side_of(seg):
            return self.distance(seg.p1)
        if not self.in_side_of(seg.reverse()):
            return self.distance(seg.p2)
        else:
            return self.distance_to_line(seg)


Vector = Point


class Segment:

    def __init__(self, p1: Point = None, p2: Point = None) -> None:
        self.p1: Point = Point() if p1 is None else p1
        self.p2: Point = Point() if p2 is None else p2

    def __repr__(self) -> str:
        return "Segment({}, {})".format(self.p1, self.p2)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Segment):
            # print("NotImplemented in Segment")
            return NotImplemented
        return self.p1 == other.p1 and self.p2 == other.p2

    def vector(self) -> Vector:
        return self.p2 - self.p1

    def reverse(self) -> 'Segment':
        return Segment(self.p2, self.p1)

    def length(self) -> float:
        return self.p1.distance(self.p2)

    def is_orthogonal(self, other: 'Segment') -> bool:
        return self.vector().is_orthogonal(other.vector())

    def is_parallel(self, other: 'Segment') -> bool:
        return self.vector().is_parallel(other.vector())

    def projection(self, p: Point) -> Point:
        v = self.vector()
        vp = p - self.p1
        return v.dot(vp) / v.norm() * v + self.p1

    def reflection(self, p: Point) -> Point:
        x = self.projection(p)
        return p + 2 * (x - p)

    def intersect_ratio(self, other: 'Segment') -> Tuple[float, float]:
        a = self.vector()
        b = other.vector()
        c = self.p1 - other.p1
        s = b.cross(c) / a.cross(b)
        t = a.cross(c) / a.cross(b)
        return s, t

    def intersects(self, other: 'Segment') -> bool:
        s, t = self.intersect_ratio(other)
        return (0 <= s <= 1) and (0 <= t <= 1)

    def intersection(self, other: 'Segment') -> Point:
        s, _ = self.intersect_ratio(other)
        return self.p1 + s * self.vector()

    def distance_with_segment(self, other: 'Segment') -> float:
        if not self.is_parallel(other) and \
                self.intersects(other):
            return 0
        else:
            return min(
                self.p1.distance_to_segment(other),
                self.p2.distance_to_segment(other),
                other.p1.distance_to_segment(self),
                other.p2.distance_to_segment(self))


Line = Segment


class Circle:

    def __init__(self, c: Point=None, r: float=0.0) -> None:
        self.c: Point = Point() if c is None else c
        self.r: float = r

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Circle):
            return NotImplemented
        return self.c == other.c and self.r == other.r

    def __repr__(self) -> str:
        return "Circle({}, {})".format(self.c, self.r)
       
def main() -> None:
    n = int(input())

    for _ in range(n):
        x1, y1, x2, y2, x3, y3, x4, y4 = [int(x) for x in input().split()]
        s1 = Segment(Point(x1, y1), Point(x2, y2))
        s2 = Segment(Point(x3, y3), Point(x4, y4))
        print(s1.distance_with_segment(s2))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import math

EPS = 1e-10

class Vector:
    def __init__(self, x=None, y=None):
        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, k):
        return Vector(self.x * k, self.y * k)

    def __gt__(self, other):
        return self.x > other.x and self.y > other.yb

    def __lt__(self, other):
        return self.x < other.x and self.y < other.yb

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

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

    # usually cross operation return Vector but it returns scalor
    def cross(self, other):
        return self.x * other.y - self.y * other.x

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

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

class Point(Vector):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

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

def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > EPS:
        return 1
    elif a.cross(b) < -EPS:
        return -1
    elif a.dot(b) < -EPS:
        return 2
    elif a.norm() < b.norm():
        return -2
    else:
        return 0

def intersect(*args, **kwargs):
    # input two segments
    if len(args) == 2:
        s1, s2 = args
        return (ccw(s1.p1, s1.p2, s2.p1) * ccw(s1.p1, s1.p2, s2.p2) <= 0 and
                    ccw(s2.p1, s2.p2, s1.p1) * ccw(s2.p1, s2.p2, s1.p2) <= 0)
    # input four points
    elif len(args) == 4:
        p0, p1, p2, p3 = args
        return (ccw(p0, p1, p2) * ccw(p0, p1, p3) <= 0 and
                    ccw(p2, p3, p0) * ccw(p2, p3, p1) <= 0)
    else:
        raise ArgsError

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

def get_distance_sp(s, p):
    v1 = s.p2 - s.p1
    v2 = p - s.p1
    v3 = s.p1 - s.p2
    v4 = p - s.p2
    if v1.dot(v2) < 0:
        return v2.abs()
    elif v3.dot(v4) < 0:
        return v4.abs()
    else:
        return get_distance_lp(s, p)

def get_distance(*args, **kwargs):
    # input two points with the startpoint (0, 0)
    if len(args) == 2:
        p1, p2 = args
        v = p1 - p2
        return v.abs()
    # input two segments
    elif len(kwargs) == 2:
        s1 = kwargs['s1']
        s2 = kwargs['s2']
        if intersect(s1, s2):
            return 0.0
        else:
            return min(min(get_distance_sp(s1, s2.p1), get_distance_sp(s1, s2.p2)),
                        min(get_distance_sp(s2, s1.p1), get_distance_sp(s2, s1.p2)))
    else:
        raise ArgsError

def read_and_print_results(n):
    for _ in range(n):
        line = stdin.readline().strip().split()
        p0 = Vector(int(line[0]), int(line[1]))
        p1 = Vector(int(line[2]), int(line[3]))
        p2 = Vector(int(line[4]), int(line[5]))
        p3 = Vector(int(line[6]), int(line[7]))
        s1 = Segment(p0, p1)
        s2 = Segment(p2, p3)
        d = get_distance(s1=s1, s2=s2)
        print("{0:0.10f}".format(d))

n = int(input())
read_and_print_results(n)

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline



def main():
    q = int(readline())
    for i in range(q):
        xy = map(int, readline().split())
        p0, p1, p2, p3 = [x + y * 1j for x, y in zip(*[xy] * 2)]
        print('{:.10f}'.format(distance(p0, p1, p2, p3)))

def lt(a, b):
    if a.real != b.real:
        return a.real <= b.real
    return a.imag < b.imag
import itertools
def distance(p0, p1, p2, p3):
    if is_intersected_ls(p0, p1, p2, p3):
        return 0
    p = []
    for i, j in itertools.product([p0, p1], [p2, p3]):
        p.append(abs(i - j))
    for i,j,k in [(p0,p1,p2),(p0,p1,p3),(p2,p3,p0),(p2,p3,p1)]:
        tmp = intersection_of_perpendicular(i,j,k)
        if (lt(i, tmp) and lt(tmp, j)) or (lt(j, tmp) and lt(tmp, i)):
            p.append(abs(tmp - k))

    return min(p)

# line(p1, p2) point(p3)
def intersection_of_perpendicular(p1, p2, p3):
    return p1 + (p2 - p1) * projecter(p2 - p1, p3 - p1)
 
 
def projecter(a, b):
    return dot(a, b) / dot(a, a)
 
 
def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def is_intersected_ls(a1, a2, b1, b2):
    eps = 0
    if max(a1.real, a2.real) < min(b1.real, b2.real)\
      or max(b1.real, b2.real) < min(a1.real, a2.real)\
      or max(a1.imag, a2.imag) < min(b1.imag, b2.imag)\
      or max(b1.imag, b2.imag) < min(a1.imag, a2.imag):
        return False
    return (cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) <= eps)\
        and (cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) <= eps)

# http://imagingsolution.blog107.fc2.com/blog-entry-137.html
def intersection(p1, p2, p3, p4):
    a1 = p4 - p2
    b1 = p2 - p3
    b2 = p1 - p2
    s1 = cross(a1, b2) / 2
    s2 = cross(a1, b1) / 2
    c1 = p1 + (p3 - p1) * s1 / (s1 + s2)
    return c1


def cross(a, b):
    return a.real * b.imag - a.imag * b.real
main()

Submission status: Accepted

Solution code:
from itertools import starmap


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


def has_intersection(p0, p1, p2, p3):
    max_x1, min_x1 = (p0.real, p1.real) if p0.real > p1.real else (p1.real, p0.real)
    max_x2, min_x2 = (p2.real, p3.real) if p2.real > p3.real else (p3.real, p2.real)
    if max_x1 < min_x2 or max_x2 < min_x1:
        return False
    max_y1, min_y1 = (p0.imag, p1.imag) if p0.imag > p1.imag else (p1.imag, p0.imag)
    max_y2, min_y2 = (p2.imag, p3.imag) if p2.imag > p3.imag else (p3.imag, p2.imag)
    if max_y1 < min_y2 or max_y2 < min_y1:
        return False

    return cross(p1 - p0, p2 - p0) * cross(p1 - p0, p3 - p0) < 1e-6 and \
           cross(p3 - p2, p0 - p2) * cross(p3 - p2, p1 - p2) < 1e-6


def point_to_segment(p0, p1, p2):
    prod = (p1 - p0).conjugate() * (p2 - p0)
    if prod.real <= 1e-6:
        return abs(p2 - p0)
    l = abs(p1 - p0)
    d = prod.real / l
    if d >= l:
        return abs(p2 - p1)
    return abs(prod.imag) / l


q = int(input())
while q:
    q -= 1
    p0, p1, p2, p3 = starmap(complex, zip(*[map(int, input().split())] * 2))
    if has_intersection(p0, p1, p2, p3):
        print(0)
        continue

    print(min(starmap(point_to_segment, ((p0, p1, p2), (p0, p1, p3), (p2, p3, p0), (p2, p3, p1)))))

Submission status: Accepted

Solution code:
from math import sqrt
for t in xrange(input()):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, raw_input().split())
    dx0 = x1 - x0
    dy0 = y1 - y0
    dx1 = x3 - x2
    dy1 = y3 - y2

    s = (y0-y2)*dx1 - (x0-x2)*dy1
    sm = dx0*dy1 - dy0*dx1
    if s < 0:
        s = -s
        sm = -sm
    t = (y2-y0)*dx0 - (x2-x0)*dy0
    tm = dx1*dy0 - dy1*dx0
    intersection = 0
    if t < 0:
        t = -t
        tm = -tm
    dis = sqrt(
            min(
                (x2-x0)**2 + (y2-y0)**2,
                (x3-x0)**2 + (y3-y0)**2,
                (x2-x1)**2 + (y2-y1)**2,
                (x3-x1)**2 + (y3-y1)**2
                )
            )
    ov = dx0*dy1 - dy0*dx1
    if 0 <= s <= max(sm, 0) and 0 <= t <= max(tm, 0):
        if ov == 0:
            r0 = dx0**2 + dy0**2
            r1 = (x2-x0)*dx0 + (y2-y0)*dy0
            r2 = (x3-x0)*dx0 + (y3-y0)*dy0
            if r1 > r2: r1, r2 = r2, r1
            if r2 < 0 or r0 < r1:
                intersection = 0
            else:
                intersection = 1
        else:
            intersection = 1
    else:
        if ov == 0:
            r0 = dx0**2 + dy0**2
            r1 = dx0*(x2-x0) + dy0*(y2-y0)
            r2 = dx0*(x3-x0) + dy0*(y3-y0)
            if 0 <= r2 and r1 <= r0:
                dis = min(dis, abs(dx0*(y2-y0) - dy0*(x2-x0)) / sqrt(r0))
        else:
            r0 = dx0**2 + dy0**2
            r1 = dx0*(x2-x0) + dy0*(y2-y0)
            r2 = dx0*(x3-x0) + dy0*(y3-y0)
            if 0 <= r1 <= r0:
                o1 = abs(dx0*(y2-y0) - dy0*(x2-x0))
                dis = min(dis, o1 / sqrt(r0))
            if 0 <= r2 <= r0:
                o2 = abs(dx0*(y3-y0) - dy0*(x3-x0))
                dis = min(dis, o2 / sqrt(r0))
            s0 = dx1**2 + dy1**2
            s1 = dx1*(x0-x2) + dy1*(y0-y2)
            s2 = dx1*(x1-x2) + dy1*(y1-y2)
            if 0 <= s1 <= s0:
                o1 = abs(dx1*(y0-y2) - dy1*(x0-x2))
                dis = min(dis, o1 / sqrt(s0))
            if 0 <= s2 <= s0:
                o2 = abs(dx1*(y1-y2) - dy1*(x1-x2))
                dis = min(dis, o2 / sqrt(s0))

        intersection = 0
    if intersection:
        print "%.09f" % 0
    else:
        print "%.09f" % dis

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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

output:
1.0000000000
1.4142135624
0.0000000000
"""

import sys

EPS = 1e-9


class Segment(object):
    __slots__ = ('source', 'target')

    def __init__(self, source, target):
        self.source = complex(source)
        self.target = complex(target)


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 get_distance_lp(l, p):
    return abs(cross(l.target - l.source, p - l.source) / abs(l.target - l.source))


def get_distance_sp(s, p):
    if dot(s.target - s.source, p - s.source) < 0:
        return abs(p - s.source)
    elif dot(s.source - s.target, p - s.target) < 0:
        return abs(p - s.target)
    else:
        return get_distance_lp(s, p)


def check_ccw(p0, p1, p2):
    a, b = p1 - p0, p2 - p0
    if cross(a, b) > EPS:
        flag = 1
    elif cross(a, b) < -1 * EPS:
        flag = -1
    elif dot(a, b) < -1 * EPS:
        flag = 2
    elif abs(a) < abs(b):
        flag = -2
    else:
        flag = 0
    return flag


def check_intersection(p0, p1, p2, p3):
    intersected = (check_ccw(p0, p1, p2) * check_ccw(p0, p1, p3) <= 0) and \
                  (check_ccw(p2, p3, p0) * check_ccw(p2, p3, p1) <= 0)

    return intersected


def calc_distance(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1, p2, p3 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        s1, s2 = Segment(p0, p1), Segment(p2, p3)
        
        intersected = check_intersection(s1.source, s1.target, s2.source, s2.target)
        if intersected:
            distance = 0
        else:
            distance = min(min(get_distance_sp(s1, s2.source), get_distance_sp(s1, s2.target)),
                           min(get_distance_sp(s2, s1.source), get_distance_sp(s2, s1.target)))
            
        print('{ans:.10f}'.format(ans=distance))
        
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    questions = int(_input[0])
    lines = map(lambda x: x.split(), _input[1:])
    calc_distance(lines)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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

output:
1.0000000000
1.4142135624
0.0000000000
"""

import sys
from collections import namedtuple

EPS = 1e-9


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 get_distance_lp(l, p):
    return abs(cross(l.target - l.source, p - l.source) / abs(l.target - l.source))


def get_distance_sp(s, p):
    if dot(s.target - s.source, p - s.source) < 0:
        return abs(p - s.source)
    elif dot(s.source - s.target, p - s.target) < 0:
        return abs(p - s.target)
    else:
        return get_distance_lp(s, p)


def check_ccw(p0, p1, p2):
    a, b = p1 - p0, p2 - p0
    if cross(a, b) > EPS:
        flag = 1
    elif cross(a, b) < -1 * EPS:
        flag = -1
    elif dot(a, b) < -1 * EPS:
        flag = 2
    elif abs(a) < abs(b):
        flag = -2
    else:
        flag = 0
    return flag


def check_intersection(p0, p1, p2, p3):
    intersected = (check_ccw(p0, p1, p2) * check_ccw(p0, p1, p3) <= 0) and \
                  (check_ccw(p2, p3, p0) * check_ccw(p2, p3, p1) <= 0)

    return intersected


def solve(_segments):
    for segment in _segments:
        axis = tuple(map(int, segment))
        p0, p1, p2, p3 = (x + y * 1j for x, y in zip(axis[::2], axis[1::2]))
        s1, s2 = Segment(p0, p1), Segment(p2, p3)

        intersected = check_intersection(s1.source, s1.target, s2.source, s2.target)
        if intersected:
            distance = 0
        else:
            distance = min(min(get_distance_sp(s1, s2.source), get_distance_sp(s1, s2.target)),
                           min(get_distance_sp(s2, s1.source), get_distance_sp(s2, s1.target)))

        print('{ans:.10f}'.format(ans=distance))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    questions = int(_input[0])
    segments = map(lambda x: x.split(), _input[1:])
    Segment = namedtuple('Segment', ('source', 'target'))
    solve(segments)

Submission status: Accepted

Solution code:
class Point:
    def __init__(self, x , y):
        self.x = x
        self.y = y
    def __sub__(self, p):
        x_sub = self.x - p.x
        y_sub = self.y - p.y
        return Point(x_sub, y_sub)

class Vector:
    def __init__(self, p):
        self.x = p.x
        self.y = p.y
        self.norm = (p.x ** 2 + p.y ** 2) ** 0.5

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

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

def ccw(p0, p1, p2):
    a = Vector(p1 - p0)
    b = Vector(p2 - p0)
    cross_ab = cross(a, b)
    if cross_ab > 0:
        return 1
    elif cross_ab < 0:
        return -1
    elif dot(a, b) < 0:
        return 1
    elif a.norm < b.norm:
        return -1
    else:
        return 0

def intersect(p1, p2, p3, p4):
    if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0) and \
       (ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0):
        return True
    else:
        return False

def getDistanceSP(sp1, sp2, p):
    a = Vector(sp2 - sp1)
    b = Vector(p - sp1)
    if dot(a, b) < 0:
        return b.norm
    c = Vector(sp1 - sp2)
    d = Vector(p - sp2)
    if dot(c, d) < 0:
        return d.norm
    return abs(cross(a, b) / a.norm)

def getDistance(p1, p2, p3, p4):
    if intersect(p1, p2, p3, p4):
        print("0.00000000")
    else:
        d = min(getDistanceSP(p1, p2, p3), getDistanceSP(p1, p2, p4),
                getDistanceSP(p3, p4, p1), getDistanceSP(p3, p4, p2))
        print("{0:.10f}".format(d))


import sys

file_input = sys.stdin

sq = file_input.readline()

for line in file_input:
    x_p0, y_p0, x_p1, y_p1, x_p2, y_p2, x_p3, y_p3 = map(int, line.split())
    p0 = Point(x_p0, y_p0)
    p1 = Point(x_p1, y_p1)
    p2 = Point(x_p2, y_p2)
    p3 = Point(x_p3, y_p3)
    getDistance(p0, p1, p2, p3)

Submission status: Accepted

Solution code:
def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    cross_ab = cross(a, b)
    if cross_ab > 0:
        return 1
    elif cross_ab < 0:
        return -1
    elif dot(a, b) < 0:
        return 1
    elif abs(a) < abs(b):
        return -1
    else:
        return 0

def intersect(p1, p2, p3, p4):
    # p1 and p2 are end points of a segment.
    # p3 and p4 are end points of the other segment.
    if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0) and \
       (ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0):
        return True
    else:
        return False

def get_distance_sp(sp1, sp2, p):
    a = sp2 - sp1
    b = p - sp1
    if dot(a, b) < 0:
        return abs(b)
    c = sp1 - sp2
    d = p - sp2
    if dot(c, d) < 0:
        return abs(d)
    return abs(cross(a, b)) / abs(a)

def print_distance(p1, p2, p3, p4):
    # parameters are the same as intersect.
    if intersect(p1, p2, p3, p4):
        print("0.0000000000")
    else:
        d = min(get_distance_sp(p1, p2, p3), get_distance_sp(p1, p2, p4),
                get_distance_sp(p3, p4, p1), get_distance_sp(p3, p4, p2))
        print("{0:.10f}".format(d))


import sys

file_input = sys.stdin

sq = file_input.readline()

for line in file_input:
    x_p0, y_p0, x_p1, y_p1, x_p2, y_p2, x_p3, y_p3 = map(int, line.split())
    p0 = x_p0 + y_p0 * 1j
    p1 = x_p1 + y_p1 * 1j
    p2 = x_p2 + y_p2 * 1j
    p3 = x_p3 + y_p3 * 1j
    print_distance(p0, p1, p2, p3)

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 sys
from itertools import starmap
readline = sys.stdin.readline
EPS = 1e-9
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
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 norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
def reflect(s, p):
    return p + (project(s, p) - p) * 2.0
def ccw(p1, p2, p3):
    a = p2 - p1
    b = p3 - p1
    if cross(a, b) > EPS: return 1
    if cross(a, b) < -EPS: return -1
    if dot(a, b) < -EPS: return 2
    if norm(a) < norm(b): return -2
    return 0
def intersect4(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 intersect2(s1, s2):
    return intersect4(s1.fi, s1.se, s2.fi, s2.se)
def getDistance(a, b):  return abs(a - b)
def getDistanceLP(l, p):
    return abs(cross(l.se - l.fi, p - l.fi) / abs(l.se - l.fi))
def getDistanceSP(s, p):
    if dot(s.se - s.fi, p - s.fi) < 0.0: return abs(p - s.fi)
    if dot(s.fi - s.se, p - s.se) < 0.0: return abs(p - s.se)
    return getDistanceLP(s, p)
def getDistances(s1, s2):
    if intersect2(s1, s2): return 0.0
    return min(min(getDistanceSP(s1, s2.fi), getDistanceSP(s1, s2.se)),
               min(getDistanceSP(s2, s1.fi), getDistanceSP(s2, s1.se)))
n = int(readline())
for _ in [0] * n:
    li = tuple(map(int, readline().split()))
    p0, p1, p2, p3 = (x + y * 1j for x, y in zip(li[::2], li[1::2]))
    s1 = Segment(p0, p1)
    s2 = Segment(p2, p3)
    print("{0:.10f}".format(getDistances(s1, s2)))