Problem:
Cross Points of a Circe and a Line For given a circle $c$ and a line $l$, print the coordinates of the cross points of them. Input The input is given in the following format. $cx\; cy\; r$ $q$ $Line_1$ $Line_2$ : $Line_q$  In the first line, the center coordinate of the circle and its radius are given by $cx$, $cy$ and $r$. In the second line, the number of queries $q$ is given. In the following $q$ lines, as queries, $Line_i$ are given ($1 \leq i \leq q$) in the following format. $x_1\; y_1\; x_2\; y_2$ Each line is represented by two points $p1$ and $p2$ which the line crosses. The coordinate of $p1$ and $p2$ are given by ($x1$, $y1$) and ($x2$, $y2$) respectively. All input values are given in integers. Output For each query, print the coordinates of the cross points in the following rules.  If there is one cross point, print two coordinates with the same values.  Print the coordinate with smaller $x$ first. In case of a tie, print the coordinate with smaller $y$ first.  The output values should be in a decimal fraction with an error less than 0.000001. Constraints  $p1$ and $p2$ are different  The circle and line have at least one cross point  $1 \leq q \leq 1,000$  $-10,000 \leq cx, cy, x1, y1, x2, y2 \leq 10,000$  $1 \leq r \leq 10,000$  Sample Input and Output Sample Input 2 1 1
2
0 1 4 1
3 0 3 3 Sample Output 1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000

Solution (Python):


import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

class Geometry:

    EPS = 10 ** -9

    def add(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return (x1+x2, y1+y2)

    def sub(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return (x1-x2, y1-y2)

    def mul(self, a, b):
        x1, y1 = a
        if not isinstance(b, tuple):
            return (x1*b, y1*b)
        x2, y2 = b 
        return (x1*x2, y1*y2)

    def div(self, a, b):
        x1, y1 = a
        if not isinstance(b, tuple):
            return (x1/b, y1/b)
        x2, y2 = b
        return (x1/x2, y1/y2)

    def abs(self, a):
        from math import hypot
        x1, y1 = a
        return hypot(x1, y1)

    def norm(self, a):
        x, y = a
        return x**2 + y**2

    def dot(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return x1*x2 + y1*y2

    def cross(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return x1*y2 - y1*x2

    def project(self, seg, p):
        """ 線分segに対する点pの射影 """
        p1, p2 = seg
        base = self.sub(p2, p1)
        r = self.dot(self.sub(p, p1), base) / self.norm(base)
        return self.add(p1, self.mul(base, r))

    def reflect(self, seg, p):
        """ 線分segを対称軸とした点pの線対称の点 """
        return self.add(p, self.mul(self.sub(self.project(seg, p), p), 2))

    def ccw(self, p0, p1, p2):
        """ 線分p0,p1から線分p0,p2への回転方向 """
        a = self.sub(p1, p0)
        b = self.sub(p2, p0)
        
        if self.cross(a, b) > self.EPS: return 1
        
        if self.cross(a, b) < -self.EPS: return -1
        
        if self.dot(a, b) < -self.EPS: return 2
        
        if self.norm(a) < self.norm(b): return -2
        
        return 0

    def intersect(self, seg1, seg2):
        """ 線分seg1と線分seg2の交差判定 """
        p1, p2 = seg1
        p3, p4 = seg2
        return (
            self.ccw(p1, p2, p3) * self.ccw(p1, p2, p4) <= 0
            and self.ccw(p3, p4, p1) * self.ccw(p3, p4, p2) <= 0
        )

    def get_distance_LP(self, line, p):
        """ 直線lineと点pの距離 """
        p1, p2 = line
        return abs(self.cross(self.sub(p2, p1), self.sub(p, p1)) / self.abs(self.sub(p2, p1)))

    def get_distance_SP(self, seg, p):
        """ 線分segと点pの距離 """
        p1, p2 = seg
        if self.dot(self.sub(p2, p1), self.sub(p, p1)) < 0: return self.abs(self.sub(p, p1))
        if self.dot(self.sub(p1, p2), self.sub(p, p2)) < 0: return self.abs(self.sub(p, p2))
        return self.get_distance_LP(seg, p)

    def get_distance_SS(self, seg1, seg2):
        """ 線分seg1と線分seg2の距離 """
        p1, p2 = seg1
        p3, p4 = seg2
        if self.intersect(seg1, seg2): return 0
        return min(
            self.get_distance_SP(seg1, p3), self.get_distance_SP(seg1, p4),
            self.get_distance_SP(seg2, p1), self.get_distance_SP(seg2, p2),
        )

    def get_cross_pointSS(self, seg1, seg2):
        """ 線分seg1と線分seg2の交点 """
        p1, p2 = seg1
        p3, p4 = seg2
        base = self.sub(p4, p3)
        dist1 = abs(self.cross(base, self.sub(p1, p3)))
        dist2 = abs(self.cross(base, self.sub(p2, p3)))
        t = dist1 / (dist1+dist2)
        return self.add(p1, self.mul(self.sub(p2, p1), t))

    def get_cross_pointCL(self, c, line):
        """ 円cと直線lineの交点 """
        from math import sqrt
        
        x, y, r = c
        p1, p2 = line
        pr = self.project(line, (x, y))
        e = self.div(self.sub(p2, p1), self.abs(self.sub(p2, p1)))
        base = sqrt(r*r - self.norm(self.sub(pr, (x, y))))
        return [self.add(pr, self.mul(e, base)), self.sub(pr, self.mul(e, base))]

gm = Geometry()
x, y, r = MAP()
c = (x, y, r)
for _ in range(INT()):
    x1, y1, x2, y2 = MAP()
    seg = ((x1, y1), (x2, y2))
    res = gm.get_cross_pointCL(c, seg)
    res.sort()
    
    res = sum(res, ())
    for i in range(3):
        print('{:.10f}'.format(res[i]), end=' ')
    print('{:.10f}'.format(res[-1]))

Solution (Python):
from math import sqrt
EPS = 1e-8


def Projection(point, begin, end):
	tmp = (point-begin) / (end-begin)
	return tmp.real * (end-begin) + begin

x, y, r = map(int, input().split())
c = complex(x, y)
ans = []
q = int(input())
for _ in range(q):
	res = []
	x, y, z, w = map(int, input().split())
	p1, p2 = complex(x, y), complex(z, w)
	proj = Projection(c, p1, p2)
	for i in [-1, 1]:
		res.append(proj + i * sqrt(r**2 - abs(c-proj)**2) * (p2-p1) / abs(p2-p1))
	res.sort(key=lambda x: (x.real, x.imag))
	ans.append((res[0].real, res[0].imag, res[1].real, res[1].imag))
for a in ans:
	print("{:.10f} {:.10f} {:.10f} {:.10f}".format(*a))

Solution (Python):
import math


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

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

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

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

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

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

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

    def __lt__(self, v):
        if math.isclose(self.x, v.x):
            return self.y < v.y
        return self.x < v.x

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

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

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


def projection(v1, v2, p):
    v12 = (v2-v1).norm()
    v1p = p-v1
    d = v12.dot(v1p)
    return v1+v12*d


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


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


def ccw(p0, p1, p2):
    c = (p1-p0).cross(p2-p0)
    if math.isclose(c, 0.0, abs_tol=1e-10):
        d = (p1-p0).dot(p2-p0)
        if d < 0.0:
            return -1
        else:
            d1 = abs(p1-p0)
            d2 = abs(p2-p0)
            if d1 < d2:
                return 1
            else:
                return 0
    elif c < 0.0:
        return -1
    else:
        return 1


def intersect(p1, p2, p3, p4):
    '''
    p1p2とp3p4の交差判定
    '''
    
    
    
    
    
    c1 = ccw(p1, p2, p3)*ccw(p1, p2, p4)
    c2 = ccw(p3, p4, p1)*ccw(p3, p4, p2)
    return c1 <= 0.0 and c2 <= 0.0


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


cx, cy, r = map(int, input().split())
p = Vector2(cx, cy)
q = int(input())
for i in range(q):
    x1, y1, x2, y2 = map(int, input().split())
    v1, v2 = Vector2(x1, y1), Vector2(x2, y2)
    '''
    円と線分の交点
    '''
    pr = projection(v1, v2, p)
    e = (v2-v1)/abs(v2-v1)
    base = math.sqrt(r*r-abs(pr-p)**2)
    a1, a2 = pr+e*base, pr-e*base
    ans = ""
    for a in sorted([a1, a2]):
        ans += f"{a.x:.10f} {a.y:.10f} "
    print(ans.strip())

Solution (Python):


from typing import List, Tuple
from math import sqrt
from enum import IntEnum

EPS = 1e-10


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


class PointLocation(IntEnum):
    COUNTER_CLOCKWISE = 1
    CCW = 1
    CLOCKWISE = -1
    CW = -1
    ONLINE_BACK = 2
    O_B = 2
    ONLINE_FRONT = -2
    O_F = -2
    ON_SEGMENT = 0
    O_S = 0


PL = PointLocation


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

    def location(self, seg: 'Segment') -> PointLocation:
        p = self - seg.p1
        d = seg.vector().cross(p)
        if d > EPS:
            return PointLocation.COUNTER_CLOCKWISE
        if d < -EPS:
            return PointLocation.CLOCKWISE
        if seg.vector().dot(p) < 0.0:
            return PointLocation.ONLINE_BACK
        if seg.vector().norm() < p.norm():
            return PointLocation.ONLINE_FRONT
        return PointLocation.ON_SEGMENT


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):
            
            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 intersects(self, other: 'Segment') -> bool:
        d0: PointLocation = self.p1.location(other)
        d1: PointLocation = self.p2.location(other)
        d2: PointLocation = other.p1.location(self)
        d3: PointLocation = other.p2.location(self)
        return d0 * d1 * d2 * d3 == 0 or \
            (d0 * d1 == -1 and d2 * d3 == -1)

    def intersection(self, other: 'Segment') -> Point:
        a = self.vector()
        b = other.vector()
        c = self.p1 - other.p1
        s = b.cross(c) / a.cross(b)
        return self.p1 + s * a

    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 cross_point(self, line: Line) -> List[Point]:
        proj = line.projection(self.c)
        dist = self.c.distance_to_line(line)
        tan = sqrt(self.r * self.r - dist * dist)
        u = line.vector() / line.vector().abs()
        return sorted([proj - tan * u, proj + tan * u])

def main() -> None:
    cx, cy, r = [int(x) for x in input().split()]
    c = Circle(Point(cx, cy), r)
    q = int(input())

    for _ in range(q):
        x0, y0, x1, y1 = [int(x) for x in input().split()]
        line = Line(Point(x0, y0), Point(x1, y1))
        left, right = c.cross_point(line)
        print("{:.8f} {:.8f} {:.8f} {:.8f}".format(
            left.x, left.y, right.x, right.y))


if __name__ == "__main__":
    main()

Solution (Python):



from math import sqrt


def cross_point(circle, p1, p2):
    x0, y0, r = circle
    x1, y1 = p1
    x2, y2 = p2

    p1p2 = norm((x2-x1, y2-y1))
    op1 = norm((x0-x1, y0-y1))
    rr = r*r
    dp = dot((x0-x1, y0-y1), (x2-x1, y2-y1))

    d = dp*dp - p1p2 * (op1 - rr)

    if abs(d) < 1e-10:
        t = dp / p1p2
        return [(x1 + t*(x2-x1), y1 + t*(y2-y1))]
    elif d > 1e-10:
        t1 = (dp+sqrt(d)) / p1p2
        t2 = (dp-sqrt(d)) / p1p2
        return [(x1 + t1*(x2-x1), y1 + t1*(y2-y1)),
                (x1 + t2*(x2-x1), y1 + t2*(y2-y1))]
    else:
        return None


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


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


def run():
    c = [int(i) for i in input().split()]
    q = int(input())

    for _ in range(q):
        x1, y1, x2, y2 = [int(i) for i in input().split()]
        ps = cross_point(c, (x1, y1), (x2, y2))

        if ps is None:
            raise ValueError('the circle and line do not intersect')
        if len(ps) == 1:
            ps *= 2

        p1, p2 = ps
        if p1 > p2:
            p1, p2 = p2, p1

        print("{:.8f} {:.8f} {:.8f} {:.8f}".format(*p1, *p2))


if __name__ == '__main__':
    run()

Solution (Python):
cx, cy, r = map(int, input().split())
q = int(input())

for _ in range(q):
  x1,y1,x2,y2 = map(int,input().split())
  dx, dy = x2 - x1, y2 - y1
  px, py = cx - x1, cy - y1
  s2 = dx **2 + dy **2
  dot = dx*px + dy*py
  crs = dx * py - dy * px
  t1 = (dot + (s2 * r ** 2 - crs ** 2) **0.5)/s2
  t2 = (dot -(s2 * r ** 2 -crs ** 2) ** 0.5)/s2
  if (dx < 0 or (dx == 0 and dy < 0 )) ^ (t1 > t2):
    t1,t2 = t2,t1
  print(x1+dx*t1, y1+dy*t1,x1+dx*t2,y1+dy*t2)

Solution (Python):
import math

EPS = 1e-10

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


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

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

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

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

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

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

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

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

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

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


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


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


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 project(s, p):
    base = s.p2 - s.p1
    r = dot(p - s.p1, base) / base.norm()
    return s.p1 + base * r


def getCrossPoint(c, l):
    pr = project(l, c.c)
    e = (l.p2 - l.p1) / (l.p2 - l.p1).abs()
    base = math.sqrt(c.r * c.r - (pr - c.c).norm())
    return (pr + e * base, pr - e * base)


if __name__ == '__main__':
    cx, cy, r =  [int(v) for v in input().split()]
    c = Circle(Point(cx, cy), r)
    q = int(input())
    ans = []
    for i in range(q):
        x1, y1, x2, y2 = [int(v) for v in input().split()]
        l = Segment(Point(x1, y1), Point(x2, y2))
        v1, v2 = getCrossPoint(c, l)
        if v2 < v1:
            v1, v2 = v2, v1
        ans.append([v1.x, v1.y, v2.x, v2.y])

    for v in ans:
        print('{0[0]:.8f} {0[1]:.8f} {0[2]:.8f} {0[3]:.8f}'.format(v))

Solution (Python):


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

sys.setrecursionlimit(10000000)

x, y, r = map(float, raw_input().split())

q = input()

for loop in range(q):
    x1, y1, x2, y2 = map(float, raw_input().split())
    vx = x2 - x1
    vy = y2 - y1
    norm = vx * vx + vy * vy
    inn = vx * (x - x1) + vy * (y - y1)
    xc = x1 + vx * inn / norm
    yc = y1 + vy * inn / norm
    rem = math.sqrt(max(0, r ** 2 - (xc - x) ** 2 - (yc - y) ** 2))
    dx = vx / math.sqrt(norm) * rem
    dy = vy / math.sqrt(norm) * rem

    ans = sorted([(xc + dx, yc + dy), (xc - dx, yc - dy)])
    print "%.10f %.10f %.10f %.10f" % (ans[0][0], ans[0][1], ans[1][0], ans[1][1])