Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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



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

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = math.sqrt(r*r-(abs(pro-p2)**2))
  ans_small=pro-e*base
  ans_big=pro+e*base
  return ans_small.real,ans_small.imag,ans_big.real,ans_big.imag


cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print(*get_cross_point(p0,p1,p2))

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = math.sqrt(r*r-(abs(pro-p2)**2))
  if pro-e*base.real == pro+e*base.real:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.imag)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.imag)
  else:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.real)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.real)
  return ans1.real, ans1.imag,ans2.real,ans2.imag


cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print(*get_cross_point(p0,p1,p2))

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = math.sqrt(r*r-(abs(pro-p2)**2))
  if pro-e*base.real == pro+e*base.real:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.imag)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.imag)
  else:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.real)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.real)
  return ans1.real, ans1.imag,ans2.real,ans2.imag


cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print("{:.10} {:.10} {:.10} {:.10}".format(*get_cross_point(p0,p1,p2)))

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = math.sqrt(r*r-(abs(pro-p2)**2))
  if pro-e*base.real == pro+e*base.real:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.imag)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.imag)
  else:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.real)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.real)
  return ans1.real, ans1.imag,ans2.real,ans2.imag


cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print("{:.8} {:.8} {:.8} {:.8}".format(*get_cross_point(p0,p1,p2)))

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = math.sqrt(r*r-(abs(pro-p2)**2))
  if pro-e*base.real == pro+e*base.real:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.imag)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.imag)
  else:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.real)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.real)
  return ans1.real, ans1.imag,ans2.real,ans2.imag


cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print("{:.8f} {:.8f} {:.8f} {:.8f}".format(*get_cross_point(p0,p1,p2)))

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = (r**2 - abs(pro-p2)**2)**0.5
  if pro-e*base.real == pro+e*base.real:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.imag)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.imag)
  elif (pro-e*base).real < (pro+e*base).real:
    ans1=pro-e*base
    ans2=pro+e*base
  else:
    ans1=pro+e*base
    ans2=pro-e*base
  return ans1.real, ans1.imag,ans2.real,ans2.imag


cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print("{:.8f} {:.8f} {:.8f} {:.8f}".format(*get_cross_point(p0,p1,p2)))

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = (r**2 - abs(pro-p2)**2)**0.5
  if pro-e*base.real == pro+e*base.real:
    ans1=min(pro-e*base,pro+e*base,key=lambda x:x.imag)
    ans2=max(pro-e*base,pro+e*base,key=lambda x:x.imag)
  elif (pro-e*base).real < (pro+e*base).real:
    ans1=pro-e*base
    ans2=pro+e*base
  else:
    ans1=pro+e*base
    ans2=pro-e*base
  return ans1.real, ans1.imag,ans2.real,ans2.imag


cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print("{:.8f} {:.8f} {:.8f} {:.8f}".format(*get_cross_point(p0,p1,p2)))

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = (r**2 - abs(pro-p2)**2)**0.5
  if pro-e*base.real == pro+e*base.real:
    if (pro-e*base).imag < (pro+e*base).imag:
      ans1=pro-e*base
      ans2=pro+e*base
    else:
      ans1=pro+e*base
      ans2=pro-e*base
  elif (pro-e*base).real < (pro+e*base).real:
    ans1=pro-e*base
    ans2=pro+e*base
  else:
    ans1=pro+e*base
    ans2=pro-e*base
  return ans1.real, ans1.imag,ans2.real,ans2.imag

cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print("{:.8f} {:.8f} {:.8f} {:.8f}".format(*get_cross_point(p0,p1,p2)))

Submission status: Wrong Answer

Solution code:
import math
def dot(a, b):
  return a.real * b.real + a.imag * b.imag

def projection(p0,p1,p2):
  a=p1-p0
  b=p2-p0
  pro = a * dot(a, b) / (abs(a) ** 2)
  t=p0+pro
  return t

def get_cross_point(p0,p1,p2):
  pro=projection(p0,p1,p2)
  e  =(p1-p0)/abs(p1-p0)
  base = (r**2 - abs(pro-p2)**2)**0.5
  if pro-e*base.real == pro+e*base.real:
    if (pro-e*base).imag < (pro+e*base).imag:
      ans1=pro-e*base
      ans2=pro+e*base
    else:
      ans1=pro+e*base
      ans2=pro-e*base
  elif (pro-e*base).real < (pro+e*base).real:
    ans1=pro-e*base
    ans2=pro+e*base
    # print('a')
  else:
    ans2=pro+e*base
    ans1=pro-e*base
    # print('i')
  return ans1.real, ans1.imag,ans2.real,ans2.imag

cx, cy, r = map(int, input().split())
p2=complex(cx,cy)
q = int(input())
for _ in range(q):
  x0,y0,x1,y1=map(int,input().split())
  p0=complex(x0,y0)
  p1=complex(x1,y1)
  print("{:.8f} {:.8f} {:.8f} {:.8f}".format(*get_cross_point(p0,p1,p2)))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math

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 __truediv__(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

class Line(Segment):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

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

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

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

def read_and_print_results(n, c):
    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]))
        l = Line(p0, p1)
        p2, p3 = get_cross_point(c, l)
        print("{0:0.8f} {1:0.8f} {2:0.8f} {3:0.8f}".format(p2.x, p2.y, p3.x, p3.y))

x, y, r = [ int(i) for i in input().split() ]
c = Circle(Point(x, y), r)
n = int(input())
read_and_print_results(n, c)

Submission status: Wrong Answer

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

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

output:
1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000
"""

import sys
import math


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

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


class Circle(object):
    __slots__ = ('centre', 'radius')

    def __init__(self, x, y, r):
        self.centre = x + y * 1j
        self.radius = r


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


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def get_cross_point(c, l):
    prj_vector = project(l, c.centre)
    line_unit_vector = (l.target - l.source) / (abs(l.target - l.source))
    base = math.sqrt(pow(c.radius, 2) - pow(abs(prj_vector - c.centre), 2))
    return prj_vector + line_unit_vector * base, prj_vector - line_unit_vector * base


def solve(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        l = Segment(p0, p1)
        cross_pair = get_cross_point(circle, l)
        cp1, cp2 = cross_pair
        print('{0:.6f} {1:.6f} {2:.6f} {3:.6f}'.format(cp1.real, cp1.imag, cp2.real, cp2.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    cx, cy, radius = map(int, _input[0].split())
    q_num = int(_input[1])
    lines = map(lambda x: x.split(), _input[2:])

    circle = Circle(cx, cy, radius)
    solve(lines)

Submission status: Wrong Answer

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

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

output:
1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000
"""

import sys
import math
from operator import attrgetter


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

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


class Circle(object):
    __slots__ = ('centre', 'radius')

    def __init__(self, x, y, r):
        self.centre = x + y * 1j
        self.radius = r


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


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def get_cross_point(c, l):
    prj_vector = project(l, c.centre)
    line_unit_vector = (l.target - l.source) / (abs(l.target - l.source))
    base = math.sqrt(pow(c.radius, 2) - pow(abs(prj_vector - c.centre), 2))
    return prj_vector + line_unit_vector * base, prj_vector - line_unit_vector * base


def solve(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        l = Segment(p0, p1)
        cross_pair = get_cross_point(circle, l)
        cp1, cp2 = sorted(cross_pair, key=attrgetter('real'))
        print('{0:.6f} {1:.6f} {2:.6f} {3:.6f}'.format(cp1.real, cp1.imag, cp2.real, cp2.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    cx, cy, radius = map(int, _input[0].split())
    q_num = int(_input[1])
    lines = map(lambda x: x.split(), _input[2:])

    circle = Circle(cx, cy, radius)
    solve(lines)

Submission status: Wrong Answer

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

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

output:
1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000
"""

import sys
import math
from operator import attrgetter


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

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


class Circle(object):
    __slots__ = ('centre', 'radius')

    def __init__(self, x, y, r):
        self.centre = x + y * 1j
        self.radius = r


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


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def get_cross_point(c, l):
    prj_vector = project(l, c.centre)
    line_unit_vector = (l.target - l.source) / (abs(l.target - l.source))
    base = math.sqrt(pow(c.radius, 2) - pow(abs(prj_vector - c.centre), 2))
    return prj_vector + line_unit_vector * base, prj_vector - line_unit_vector * base


def solve(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        l = Segment(p0, p1)
        cross_pair = get_cross_point(circle, l)
        cp1, cp2 = sorted(cross_pair, key=attrgetter('real'))
        print('{0:.10f} {1:.10f} {2:.10f} {3:.10f}'.format(cp1.real, cp1.imag, cp2.real, cp2.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    cx, cy, radius = map(int, _input[0].split())
    q_num = int(_input[1])
    lines = map(lambda x: x.split(), _input[2:])

    circle = Circle(cx, cy, radius)
    solve(lines)

Submission status: Wrong Answer

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

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

output:
1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000
"""

import sys
import math
from operator import attrgetter


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

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


class Circle(object):
    __slots__ = ('centre', 'radius')

    def __init__(self, x, y, r):
        self.centre = x + y * 1j
        self.radius = r


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


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def get_cross_point(c, l):
    prj_vector = project(l, c.centre)
    line_unit_vector = (l.target - l.source) / (abs(l.target - l.source))
    base = math.sqrt(pow(c.radius, 2) - pow(abs(prj_vector - c.centre), 2))
    return prj_vector + line_unit_vector * base, prj_vector - line_unit_vector * base


def solve(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        l = Segment(p0, p1)
        cross_pair = get_cross_point(circle, l)
        cp1, cp2 = sorted(cross_pair, key=attrgetter('real'))
        print('{0:.8f} {1:.8f} {2:.8f} {3:.8f}'.format(cp1.real, cp1.imag, cp2.real, cp2.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    cx, cy, radius = map(int, _input[0].split())
    q_num = int(_input[1])
    lines = map(lambda x: x.split(), _input[2:])

    circle = Circle(cx, cy, radius)
    solve(lines)

Submission status: Wrong Answer

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

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

output:
1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000
"""

import sys
import math
from operator import attrgetter


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

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


class Circle(object):
    __slots__ = ('centre', 'radius')

    def __init__(self, x, y, r):
        self.centre = x + y * 1j
        self.radius = r


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


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def get_cross_point(c, l):
    prj_vector = project(l, c.centre)
    line_unit_vector = (l.target - l.source) / (abs(l.target - l.source))
    base = math.sqrt(pow(c.radius, 2) - pow(abs(prj_vector - c.centre), 2))
    return prj_vector + line_unit_vector * base, prj_vector - line_unit_vector * base


def solve(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        l = Segment(p0, p1)
        cross_pair = get_cross_point(circle, l)
        cp = sorted(cross_pair, key=attrgetter('real'))
        cp = sorted(cp, key=attrgetter('imag'))
        cp1, cp2 = cp
        print('{0:.8f} {1:.8f} {2:.8f} {3:.8f}'.format(cp1.real, cp1.imag, cp2.real, cp2.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    cx, cy, radius = map(int, _input[0].split())
    q_num = int(_input[1])
    lines = map(lambda x: x.split(), _input[2:])

    circle = Circle(cx, cy, radius)
    solve(lines)

Submission status: Wrong Answer

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

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

output:
1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000
"""

import sys
import math


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

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


class Circle(object):
    __slots__ = ('centre', 'radius')

    def __init__(self, x, y, r):
        self.centre = x + y * 1j
        self.radius = r


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


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def get_cross_point(c, l):
    prj_vector = project(l, c.centre)
    line_unit_vector = (l.target - l.source) / (abs(l.target - l.source))
    base = math.sqrt(pow(c.radius, 2) - pow(abs(prj_vector - c.centre), 2))
    p1, p2 = prj_vector + line_unit_vector * base, prj_vector - line_unit_vector * base

    if p1.real <= p2.real and p1.imag < p2.imag:
        ans = (p1, p2)
    else:
        ans = (p2, p1)
    return ans


def solve(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        l = Segment(p0, p1)
        cp1, cp2 = get_cross_point(circle, l)
        print('{0:.8f} {1:.8f} {2:.8f} {3:.8f}'.format(cp1.real, cp1.imag, cp2.real, cp2.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    cx, cy, radius = map(int, _input[0].split())
    q_num = int(_input[1])
    lines = map(lambda x: x.split(), _input[2:])

    circle = Circle(cx, cy, radius)
    solve(lines)

Submission status: Wrong Answer

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

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

output:
1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000
"""

import sys
import math


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

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


class Circle(object):
    __slots__ = ('centre', 'radius')

    def __init__(self, x, y, r):
        self.centre = x + y * 1j
        self.radius = r


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


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def get_cross_point(c, l):
    prj_vector = project(l, c.centre)
    line_unit_vector = (l.target - l.source) / (abs(l.target - l.source))
    base = math.sqrt(pow(c.radius, 2) - pow(abs(prj_vector - c.centre), 2))
    p1, p2 = prj_vector + line_unit_vector * base, prj_vector - line_unit_vector * base

    if p1.real <= p2.real and p1.imag <= p2.imag:
        ans = (p1, p2)
    else:
        ans = (p2, p1)
    return ans


def solve(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        l = Segment(p0, p1)
        cp1, cp2 = get_cross_point(circle, l)
        print('{0:.8f} {1:.8f} {2:.8f} {3:.8f}'.format(cp1.real, cp1.imag, cp2.real, cp2.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    cx, cy, radius = map(int, _input[0].split())
    q_num = int(_input[1])
    lines = map(lambda x: x.split(), _input[2:])

    circle = Circle(cx, cy, radius)
    solve(lines)

Submission status: Wrong Answer

Solution code:
def solve_eq(a,b,c):
    return (-b-(b**2-4*a*c)**0.5)/2*a,(-b+(b**2-4*a*c)**0.5)/2*a

def ret_line(x1,y1,x2,y2):
    k = (y1-y2)/(x1-x2)
    d = y1-k*x1
    return k,d
    
x,y,r = map(float,input().split())
q = int(input())
x1,y1,x2,y2 = [],[],[],[]
for i in range(q):
    arr = list(map(float,input().split()))
    x1.append(arr[0])
    y1.append(arr[1])
    x2.append(arr[2])
    y2.append(arr[3])

for i in range(q):
    if x1[i] != x2[i]:
        k,d = ret_line(x1[i],y1[i],x2[i],y2[i])
        p1,p2 = solve_eq(1+k**2,2*k*d-2*k*x-2*x,x**2+y**2+d**2-2*y*d-r**2)
        print(p1,k*p1+d,p2,k*p2+d)
    if x1[i] == x2[i]:
        p1,p2 = solve_eq(1,-2*y,y**2+(x1[i]-x)**2-r**2)
        print(x1[i],p1,x1[i],p2)

Submission status: Wrong Answer

Solution code:
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) ^ (t1 > t2):
        t1, t2 = t2, t1
    print(x1 + dx * t1, y1 + dy * t1, x1 + dx * t2, y1 + dy * t2)

Submission status: Wrong Answer

Solution code:
from math import sqrt
cx,cy,r = map(int,input().split())
c = [cx, cy]
q = int(input())

class Line:pass

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])
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)    
def proj(p, l):
    base = sub(l.p2, l.p1)
    hypo = sub(p, l.p1)
    t = dot(hypo,base) / norm(base)
    return add(l.p1, multi(t/norm(base), base))
    
for i in range(q):
    x1,y1,x2,y2 = map(int, input().split())
    l = Line()
    l.p1 = [x1,y1]
    l.p2 = [x2,y2]
    pr = proj(c, l)
    e = multi(1/norm(sub(l.p2, l.p1)),sub(l.p2, l.p1))
    e2 = multi(-1, e)
    base = sqrt(r**2 - norm(sub(pr,c))**2)
    a = add(pr, multi(base, e))
    b = add(pr, multi(base, e2))
    ans = [a,b]
    ans = sorted(ans, key=lambda x: (x[0],x[1]))
    print(' '.join([str(i) for o in ans for i in o]))

Submission status: Wrong Answer

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 project(l, p):
    p1, p2 = l
    base = p2 - p1
    hypo = p - p1
    return p1 + base * (hypo.dot(base) / abs(base)**2)


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


def getCrossPoints(c, l):
    pr = project(l, c.c)
    p1, p2 = l
    e = (p2 - p1) * (1 / abs(p2 - p1))
    base = math.sqrt(c.r**2 - abs(pr - c.c)**2)
    return [pr + e * base, pr - e * base]


if __name__ == '__main__':

    a, b, r = map(int, input().split())
    c = Circle(Vector2(a, b), r)
    n = int(input())
    for _ in range(n):
        ps = list(map(int, input().split()))
        l = [Vector2(ps[0], ps[1]), Vector2(ps[2], ps[3])]

        ans = getCrossPoints(c, l)
        ans = sorted(ans, key=lambda x: (x.x, x.y))
        print(ans[0].x, ans[0].y, ans[1].x, ans[1].y)