Problem:

Cross Point

For given two segments s1 and s2, print the coordinate of the cross point of 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 coordinate of the cross point. 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.

The given segments have a cross point and are not in parallel.

Sample Input

3
0 0 2 0 1 1 1 -1
0 0 1 1 0 1 1 0
0 0 1 1 1 0 0 1

Sample Output

1.0000000000 0.0000000000
0.5000000000 0.5000000000
0.5000000000 0.5000000000



Sample input:
3
0 0 2 0 1 1 1 -1
0 0 1 1 0 1 1 0
0 0 1 1 1 0 0 1


Sample output:
1.0000000000 0.0000000000
0.5000000000 0.5000000000
0.5000000000 0.5000000000

Submission status: Accepted

Solution code:
def cp(a,b,c,d,e,f,g,h):
    A = a*d-b*c
    B = e*h-f*g
    C = d-b
    D = e-g
    E = c-a
    F = f-h
    det = C*D - E*F
    return [(A*D + B*E)/det,(A*F + B*C)/det]

q = int(input())
for i in range(q):
    a,b,c,d,e,f,g,h = [int(i) for i in input().split()]
    P = cp(a,b,c,d,e,f,g,h)
    print(P[0],P[1])

Submission status: Accepted

Solution code:
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*d-b*c
    B = e*h-f*g
    C = d-b
    D = c-a
    E = f-h
    F = e-g
    det = C*F - D*E
    print((A*F + B*D)/det,(A*E + B*C)/det)

Submission status: Accepted

Solution code:
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*d-b*c
    B = e*h-f*g
    C = d-b
    D = c-a
    E = f-h
    F = e-g
    G = C*F - D*E
    print((A*F + B*D)/G,(A*E + B*C)/G)

Submission status: Accepted

Solution code:
q = int(input())
for i in range(q):
    a,b,c,d,e,f,g,h = [int(i) for i in input().split()]
    A = d-b
    B = c-a
    C = f-h
    D = e-g
    E = a*d-b*c
    F = e*h-f*g
    G = A*D-B*C
    print((E*D+F*B)/G,(E*C+F*A)/G)

Submission status: Accepted

Solution code:
# Aizu Problem CGL_2_C: Cross Point
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")



n = int(input())
for k in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = [int(_) for _ in input().split()]
    x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / \
        ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4))
    y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / \
        ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4))
    print("%.10f %.10f" % (x, y))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline


class Point(object):
    epsilon = 1e-10

    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        else:
            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(other * self.x, other * self.y)

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

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

    def __eq__(self, other):
        from math import fabs
        if fabs(self.x - other.x) < Point.epsilon and fabs(self.y - other.y) < Point.epsilon:
            return True
        else:
            return False

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

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


class Vector(Point):
    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        elif isinstance(x, Point):
            self.x = x.x
            self.y = x.y
        else:
            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, other):
        return Vector(other * self.x, other * self.y)

    def __truediv__(self, other):
        return Vector(other / self.x, other / self.y)

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

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

    @classmethod
    def is_orthogonal(cls, a, b):
        return Vector.dot(a, b) == 0.0

    @classmethod
    def is_parallel(cls, a, b):
        return Vector.cross(a, b) == 0.0


class Segment(object):
    def __init__(self, p1=Point(), p2=Point()):
        if isinstance(p1, Point):
            self.p1 = p1
            self.p2 = p2
        elif isinstance(p1, tuple):
            self.p1 = Point(p1[0], p1[1])
            self.p2 = Point(p2[0], p2[1])

    @classmethod
    def is_orthogonal(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_orthogonal(a, b)

    @classmethod
    def is_parallel(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_parallel(a, b)


class Line(Segment):
    pass


class Cirle(object):
    def __init__(self, c=Point(), r=0.0):
        self.c = c
        self.r = r


def ccw(p0, p1, p2):
    a = Vector(p1 - p0)
    b = Vector(p2 - p0)
    epsilon = 1e-10
    if Vector.cross(a, b) > epsilon:
        return 1 # 'COUNTER_CLOCKWISE'
    elif Vector.cross(a, b) < -epsilon:
        return -1 # 'CLOCKWISE'
    elif Vector.dot(a, b) < -epsilon:
        return 2 # 'ONLINE_BACK'
    elif a.norm() < b.norm():
        return -2 # 'ONLINE_FRONT'
    else:
        return 0 # 'ON_SEGMENT'


def cross_point(s1, s2):
    base = s2.p2 - s2.p1
    d1 = abs(Vector.cross(base, s1.p1-s2.p1))
    d2 = abs(Vector.cross(base, s1.p2-s2.p1))
    t = d1 / (d1 + d2)
    return s1.p1 + (s1.p2 - s1.p1) * t


def main(args):
    q = int(input())
    for _ in range(q):
        x_p0, y_p0, x_p1, y_p1, x_p2, y_p2, x_p3, y_p3 = map(int, input().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)
        s1 = Segment(p0, p1)
        s2 = Segment(p2, p3)
        result = cross_point(s1, s2)
        print('{:.10f} {:.10f}'.format(result.x, result.y))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from math import sqrt
q = int(input())

class Segment:pass

def add(a,b):
    return [a[0] + b[0],a[1] + b[1]]
def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]
def multi(k, a):
    return [k*a[0],k*a[1]]
def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]
def norm(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)    
    
for i in range(q):
    xp0,yp0,xp1,yp1,xp2,yp2,xp3,yp3 = map(int, input().split())
    s1 = Segment()
    s2 = Segment()
    s1.p1 = [xp0, yp0]
    s1.p2 = [xp1, yp1]
    s2.p1 = [xp2, yp2]
    s2.p2 = [xp3, yp3]    
    base = sub(s2.p2, s2.p1)
    d1 = abs(cross(base, (sub(s1.p1, s2.p1))))/norm(base)
    d2 = abs(cross(base, (sub(s1.p2, s2.p1))))/norm(base)
    t = d1/(d1+d2)
    x = add(s1.p1 , multi(t,sub(s1.p2, s1.p1)))
    print(x[0],x[1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import collections
import math


class Vector2(collections.namedtuple("Vector2", ["x",  "y"])):

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

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

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

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

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

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

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

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


def getDistanceSP(segment, point):
    p = point
    p1, p2 = segment
    if (p2 - p1).dot(p - p1) < 0:
        return abs(p - p1)
    if (p1 - p2).dot(p - p2) < 0:
        return abs(p - p2)
    return abs((p2 - p1).cross(p - p1)) / abs(p2 - p1)


def getDistance(s1, s2):
    a, b = s1
    c, d = s2
    if intersect(s1, s2):  # intersect
        return 0
    return min(getDistanceSP(s1, c), getDistanceSP(s1, d), getDistanceSP(s2, a), getDistanceSP(s2, b))


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


def intersect(s1, s2):
    a, b = s1
    c, d = s2
    return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0


def getCrossPoint(s1, s2):
    a, b = s1
    c, d = s2
    base = d - c
    d1 = abs(base.cross(a - c))
    d2 = abs(base.cross(b - c))
    t = d1 / (d1 + d2)
    return a + (b - a) * t


if __name__ == '__main__':

    n = int(input())

    for _ in range(n):
        l = list(map(int, input().split()))
        s1 = [Vector2(l[0], l[1]), Vector2(l[2], l[3])]
        s2 = [Vector2(l[4], l[5]), Vector2(l[6], l[7])]

        x = getCrossPoint(s1, s2)
        print(x.x, x.y)

Submission status: Accepted

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

class Segment():
    def __init__(self, x1, y1, x2, y2):
        self.p1 = Point(x1, y1)
        self.p2 = Point(x2, y2)
        if self.p1.x == self.p2.x:
            self.a = float('inf')
            self.b = None
        else:
            self.a = (self.p1.y - self.p2.y)/(self.p1.x - self.p2.x)
            self.b = self.p1.y - self.a*self.p1.x

    def is_intersect(self, seg):
        a = (seg.p1.x - seg.p2.x) * (self.p1.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p1.x)
        b = (seg.p1.x - seg.p2.x) * (self.p2.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p2.x)
        c = (self.p1.x - self.p2.x) * (seg.p1.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p1.x)
        d = (self.p1.x - self.p2.x) * (seg.p2.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p2.x)
        e = (self.p1.x - seg.p1.x)*(self.p2.x - seg.p2.x)
        f = (self.p1.x - seg.p2.x)*(self.p2.x - seg.p1.x)
        g = (self.p1.y - seg.p1.y)*(self.p2.y - seg.p2.y)
        h = (self.p1.y - seg.p2.y)*(self.p2.y - seg.p1.y)
        return a*b <= 0 and c*d <= 0 and (e <= 0 or f <= 0) and (g <= 0 or h <= 0)

    def cross_point(self, seg):
        if self.is_intersect(seg) == False: return None
        if self.a == float('inf'):
            return self.p1.x, seg.a * self.p1.x + seg.b
        elif seg.a == float('inf'):
            return seg.p1.x, self.a * seg.p1.x + self.b
        else:
            x = -(self.b - seg.b)/(self.a - seg.a)
            y = seg.a * x + seg.b
            return x, y

q = int(input())
for i in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = list(map(int, input().split(' ')))
    line1, line2 = Segment(x0, y0, x1, y1), Segment(x2, y2, x3, y3)
    x, y = line1.cross_point(line2)
    print('%.8f %.8f'%(x, y))

Submission status: Accepted

Solution code:
import math
EPS=1e-14

#点类
class Point():

    def __init__(self,x,y):
        self.x=x
        self.y=y
    
    def __sub__(self,p):
        return Point(self.x - p.x, self.y - p.y);
    def __add__(self,p):
        return Point(self.x + p.x, self.y + p.y)
           
    def __mul__(self,a): #a: scalar
        return Point(self.x * a, self.y * a)
    def __truediv__(self,a): #a: scalar
        return Point(self.x / a, self.y / a)
   
    def __str__(self):
       return  str(self.x)+','+str(self.y)
    def __repr__(self):
        return  'Point('+str(self.x)+','+str(self.y)+')'
    
    def __lt__(self, other):    
        if self.y-other.y==0:
            return self.x<other.x
        else:
            return self.y<other.y
            
    def __eq__(self, other):    
        return abs(self.x-other.x)<EPS and  abs(self.y-other.y)<EPS


# 线段类
class Segment():
    def __init__(self,p1, p2):
        self.p1=p1
        self.p2=p2
    def __str__(self):
        return  'segment:('+str(self.p1)+';'+str(self.p2)+')'
    def __repr__(self):
        return  'segment:('+str(self.p1)+';'+str(self.p2)+')'


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

    def __str__(self):
       return  'Circle:(center point: '+str(self.c)+'; radius: '+str(self.r)+')'
    def __repr__(self):
       return  'Circle:(center point: '+str(self.c)+'; radius: '+str(self.r)+')'
   
    
#定义多边形
class Polygon():
    def __init__(self,ps=[]):
        self.ps=ps
        self.size=len(ps)
  
    def __getitem__(self, i):#iter override 
        return self.ps[i]  
    def __setitem__(self,i,p): 
        self.ps[i]=p               
    def __iter__(self):     
        return self.ps  
    
    def addpoint(self,i,p):
        self.ps.insert(i,p)
        self.size+=1
    def delpoint(self,i):
        self.size-=1
        return self.ps.pop(i)
    def sortYX(self):
        self.ps.sort()
        #self.ps.sort(key=attrgetter('y','x'))
    def __str__(self):
       return  'Polygon:'+str(tuple(self.ps))
    def __repr__(self):
       return  'Polygon:'+str(tuple(self.ps))
        
    def __len__(self):
        return len(self.ps)
    def __eq__(self, other):  
         return self.ps==other.ps
    
    def draw(self):
      
       turtle.screensize(800,800,"black")
       #turtle.setup(width=0.9,height=0.9)
       turtle.title("Polygon convex hull")
       turtle.setworldcoordinates(-400,-400,400,400) 

       #print(turtle.screensize())
       #mywin = turtle.Screen()    
       #mywin.   
       t=turtle.Turtle() 
       #mywin=turtle.Screen()
       
       t.pencolor("red")
       for pt in self.ps:
           t.goto(pt.x,pt.y)
           t.dot(10,'white')
       
 

#***************************点、向量****************************

#向量的模的平方
def norm(p):  
    return p.x * p.x + p.y * p.y


#向量P的长度
def length(p):
    return math.sqrt(p.x * p.x + p.y * p.y)


# 向量的(点)内积, dot(a,b)=|a|*|b|*cos(a,b) (从a,到b的角)
# =============================================================================
# r=dot(a,b),得到矢量a和b的点积，如果两个矢量都非零矢量  
# r<0：两矢量夹角为钝角； 
# r=0：两矢量夹角为直角； 
# r>0：两矢量夹角为锐角  
# =============================================================================
def dot(a, b) :
    return a.x * b.x + a.y * b.y



# =============================================================================
# # 向量的（叉）外积 cross(a,b)=|a||b|*sin(a,b) (从a,到b的角)由a,b构成的平行四边的面积
# r=cross(a,b),得到向量a和向量b的叉积  
# r>0：b在矢量a的逆时针方向；  
# r=0：a,b 平行共线；  
# r<0：b在向量a的顺时针方向 
# =============================================================================
def cross( a, b) :
    return a.x * b.y - a.y * b.x

# 点p在线段s上的投影
def project(s, p):
    base = s.p2 - s.p1
    r = dot(p - s.p1, base) / norm(base)
    return s.p1 + base * r 


# 点a到点b的距离
def getDistance(a, b) :
    return length(a - b)

# 线段l和点p的距离
def getDistanceLP(l, p) :
    return abs( cross(l.p2 - l.p1, p - l.p1) / length(l.p2 - l.p1) )

#getDistanceLP(s3, p7)
    
#线段s与点p的距离
def getDistanceSP(s, p) :
    if (dot(s.p2 - s.p1, p - s.p1) < 0.0):
        return length(p - s.p1)
    if (dot(s.p1 - s.p2, p - s.p2) < 0.0):
        return length(p - s.p2)
    return getDistanceLP(s, p)

#print(getDistanceLP(s3, Point(5,5)))
#print(getDistanceSP(s3, Point(5,5)))


#*************************线段********************************/
# 线段s1，s2是否正交 <==> 内积为0
def isOrthogonalSG(s1, s2) :
    return abs(dot(s1.p2 - s1.p1, s2.p2 - s2.p1))<EPS


# 线段s1，s2是否平行 <==> 叉积为0
def isParallelLN(s1,s2) :
    return abs(cross(s1.p2 - s1.p1, s2.p2 - s2.p1))<0




# 逆时针方向ccw（Counter-Clockwise）
COUNTER_CLOCKWISE = 1;
CLOCKWISE = -1;
ONLINE_BACK = -2;
ONLINE_FRONT = 2;
ON_SEGMENT = 0;

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 (norm(a) < norm(b)):
        return ONLINE_FRONT
    
    return ON_SEGMENT;


def toleft(p0,p1,p2):
    a = p1 - p0
    b = p2 - p0  
    tmp=cross(a,b)
    if tmp > EPS:
        return 1
    elif abs(tmp)<EPS and norm(a)<=norm(b):
        return 2  #共线，p2在p0p1的右延长线上
    elif abs(tmp)<EPS and norm(a)>norm(b):
        return -2  #共线，p2在p0p1的left延长线上    
    else:
        return -1


#以线段s为对称轴与点p成线对称的点
def reflect(s, p) :
    return p + (project(s, p) - p) * 2.0



#判断线段s1和s2是否相交
def intersectSG(s1, s2) :
    return intersectP4(s1.p1, s1.p2, s2.p1, s2.p2)


# 线段s1和线段s2的距离
def getDistanceSG(s1, s2) :
    # 相交
    if (intersectSG(s1, s2)):
        return 0.0
    return min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2),\
        getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2))

# 判断线段p1p2和线段p3p4是否相交
def intersectP4(p1, p2, p3, p4) :
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and \
            ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0


# 线段s1与线段s2的交点
def getCrossPoint(s1,s2) :
    base = s2.p2 - s2.p1;
    d1 = abs(cross(base, s1.p1 - s2.p1));
    d2 = abs(cross(base, s1.p2 - s2.p1));
    if d1+d2==0:
        return s2.p1
    t = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;
                                                                                                                                                       


q=int(input())
for i in range(0,q):
    s= [int(x) for x in input().split()]
    p0=Point(s[0],s[1])
    p1=Point(s[2],s[3])
    p2=Point(s[4],s[5])
    p3=Point(s[6],s[7])
    s1=Segment(p0,p1)
    s2=Segment(p2,p3)
    
    if p0==p2 or p0==p3:
        print("{:.12f} {:.12f}".format(p0.x,p0.y))
    elif p1==p2 or p1==p3:
        print("{:.12f} {:.12f}".format(p1.x,p1.y))
    else:
        rt=getCrossPoint(s1,s2)
        print("{:.12f} {:.12f}".format(rt.x,rt.y))

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
    
    
    
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)
    
    k = cross(p2-p4,p3-p4)/cross(p3-p4,p1-p2)
    ans = k*(p1-p2)+p2
    
    print("{} {}".format(ans.x,ans.y))

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 __isub__(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:
    """
    線分クラス

    methods
    length()                 :
    get_unit_vec()           : 
    projection(vector)       :
    is_vertical(segment)     :
    is_horizontal(segment)   :
    reflection()             :
    include()                :
    distance()               :
    ccw()                    :
    intersect()              :
    """
    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)か
        ただし、直線上にはあるが線分上にはない場合は反時計回りの位置にあると判定して1を返す。
        """
        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
    
    def intersect_point(self,segment):
        d1 = norm(self.projection(segment.v1) - segment.v1)
        d2 = norm(self.projection(segment.v2) - segment.v2)
        return segment.v1 + (d1/(d1 + d2)) * (segment.v2 - segment.v1)


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




q = int(input())
tmp = [0]*q
for i in range(q):
    tmp[i] = list(map(int,input().split()))

for i in range(q):
    p0,p1,p2,p3 = Vector(tmp[i][0:2]),Vector(tmp[i][2:4]),Vector(tmp[i][4:6]),Vector(tmp[i][6:8])
    S1 = Segment(p0,p1)
    S2 = Segment(p2,p3)
    print(*S1.intersect_point(S2))

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)

def get_cross_point(s1, s2):
    base = s2.p2 - s2.p1
    d1 = abs(cross(base, s1.p1 - s2.p1))
    d2 = abs(cross(base, s1.p2 - s2.p1))
    t = d1 / (d1 + d2)
    return s1.p1 + (s1.p2 - s1.p1) * t


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_cross_point(s1, s2))