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
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   # counter clockwise
        elif cross < 0:
            return 1    # clockwise
        else:           # cross == 0
            dot = self.dot(vec_pt1_to_pt)
            if dot < 0:
                return -2    # online back
            else:       # dot > 0
                if self.abs() < vec_pt1_to_pt.abs():
                    return 2    # online front
                else:
                    return 0    # on segment

    def cross_point(self, other) -> Point:
        d1 = abs(self.cross(Vector(self.pt1, other.pt1)))       # / self.abs()
        d2 = abs(self.cross(Vector(self.pt1, other.pt2)))       # / self.abs()
        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()

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env 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())
    #(y1 - y0)(x - x0) = (x1 - x0)(y - y0)
    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

Submission status: Runtime Error

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

"""
input:
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

output:
INF
0
-5
-3

OR
input:
4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0

output:
NEGATIVE CYCLE
"""

import sys
from math import isinf


def generate_adj_table(_v_info):
    for each in _v_info:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
    return init_adj_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for current, current_info in enumerate(adj_table):
            for adj, cost in current_info.items():
                if distance[current] + cost < distance[adj]:
                    distance[adj] = distance[current] + cost

    for current, current_info in enumerate(adj_table):
        for adj, cost in current_info.items():
            if distance[current] + cost < distance[adj]:
                print('NEGATIVE CYCLE')
                return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    distance = [float('inf')] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

Submission status: Runtime Error

Solution code:
class Line:
    def __init__(self,p1,p2):
        if p1[1] < p2[1]:self.s=p2;self.e=p1
        elif p1[1] > p2[1]:self.s=p1;self.e=p2
        else:
            if p1[0] < p2[0]:self.s=p1;self.e=p2
            else:self.s=p2;self.e=p1

def cross(a,b):return a[0]*b[1] - a[1]*b[0]
def dot(a,b):return a[0]*b[0]+a[1]*b[1]
def dif(a,b):return [x-y for x,y in zip(a,b)]
def dist(a,b):return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
def isec(l,m):
    a = dif(l.e,l.s);b = dif(m.e,l.s);c = dif(m.s,l.s)
    d = dif(m.e,m.s);e = dif(l.e,m.s);f = dif(l.s,m.s)
    g = lambda a, b : cross(a,b)==0 and dot(a,b)>0 and dot(b,b)<dot(a,a)
    if g(a,b) or g(a,c) or g(d,e) or g(d,f):return True
    elif l.s == m.e or l.s == m.s or l.e == m.e or l.e == m.s:return True
    elif cross(a,b) * cross(a,c) >= 0 or cross(d,e) * cross(d,f) >= 0:return False
    else:return True
def projection(a,b):return [x*dot(a,b)/dot(a,a) for x in a]
def proj(A,B,C,D):
    AB = dif(B,A) ; AC = dif(C,A) ; AD = dif(D,A)
    CD = dif(D,C) ; CA = dif(A,C) ; CB = dif(B,C)
    _A = projection(CA,CD)
    _B = projection(CB,CD)
    _C = projection(AC,AB)
    _D = projection(AD,AB)
    return [_A,_B,_C,_D]
def Order(a,b):
    crs = cross(a,b)
    if crs > 0 : return "COUNTER_CLOCKWISE"
    elif crs < 0 : return "CLOCKWISE"
    else:
        if dot(a,b) < 0 : return "ONLINE_BACK"
        elif dot(a,a) < dot(b,b) : return "ONLINE_FRONT"
        else : return "ON_SEGMENT"


q = int(input())
for i in range(q):
    a,b,c,d,e,f,g,h = [int(i) for i in input().split()]
    A = [a,b] ; B = [c,d] ; C = [e,f] ; D = [g,h]
    l = Line(A,B) ; m = Line(C,D)
    if isec(l,m):
        print(0.0)
        continue
    _A,_B,_C,_D = proj(A,B,C,D)
    AB = dif(B,A) ; CD = dif(D,C)
    A_C = dif(_C,A) ; A_D = dif(_D,A) ; C_A = dif(_A,C) ; C_B = dif(_B,C)
    DIST = [dist(A,C),dist(A,D),dist(B,C),dist(B,D),dist(_A,A),dist(_B,B),dist(_C,C),dist(_D,D)]
    fun = lambda x : x != "ON_SEGMENT"
    if fun(Order(CD,C_A)) : DIST[4] = sys.maxsize
    if fun(Order(CD,C_B)) : DIST[5] = sys.maxsize
    if fun(Order(AB,A_C)) : DIST[6] = sys.maxsize
    if fun(Order(AB,A_D)) : DIST[7] = sys.maxsize
    print(min(DIST))