Problem:


Projection

For given three points p1, p2, p, find the projection point x of p onto p1p2.

Input

xp1 yp1 xp2 yp2
q
xp0 yp0
xp1 yp1
...
xpq&minus;1 ypq&minus;1

In the first line, integer coordinates of p1 and p2 are given. Then, q queries are given for integer coordinates of p.

Output

xt0 yt0
xt1 yt1
...
xtq-1 ytq-1

-->

For each query, print the coordinate of the projection point x. The output values should be in a decimal fraction with an error less than 0.00000001.

Constraints

1 ≤ q ≤ 1000

-10000 ≤ xi, yi ≤ 10000

p1 and p2 are not identical.

Sample Input 1

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

Sample Output 1

-1.0000000000 0.0000000000
0.0000000000 0.0000000000
1.0000000000 0.0000000000

Sample Input 2

0 0 3 4
1
2 5

Sample Output 2

3.1200000000 4.1600000000



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


Sample output:
-1.0000000000 0.0000000000
0.0000000000 0.0000000000
1.0000000000 0.0000000000

Submission status: Accepted

Solution code:
import math

def equals(a, b):
    return abs(a - b) < 1e-10


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


if __name__ == '__main__':
    x1, y1, x2, y2 = [int(v) for v in input().split()]
    s = Segment(Point(x1, y1), Point(x2, y2))
    q = int(input())
    ans = []
    for i in range(q):
        x, y = [int(v) for v in input().split()]
        p = Point(x, y)
        ans.append(project(s, p))

    for v in ans:
        print('{0:.10f} {1:.10f}'.format(v.x, v.y))

Submission status: Accepted

Solution code:
x,y,s,t = map(float, input().split())
a = int(input())
s-=x
t-=y
while a:
    a -= 1
    p,q = map(float, input().split())
    p-=x
    q-=y
    ans_x = s*(q*t+p*s)/(t*t+s*s)
    ans_y = t*(q*t+p*s)/(t*t+s*s)
    print(x+ans_x, y+ans_y)

Submission status: Runtime Error

Solution code:
x1,y1,x2,y2=map(float,raw_input().split(" "))
if y1==y2 or x1==x2:
    if y1==y2:
        t0=0
    if x1==x2:
        t1=0
else:
    t0=(y2-y1)/(x2-x1)
    b0=y1-t0*x1
    t1=-(x2-x1)/(y2-y1)

for i in xrange(int(raw_input())):
    px,py=map(float,raw_input().split(" "))
    if t0==0 or t1==0:
        if t0==0:
            t1=-1
            a=1.0
            b=-t0
            c=y1
            d=0.0
            e=-t1
            f=px
        if t1==0:
            t0=-1
            a=0.0
            b=-t0
            c=x1
            d=1.0
            e=-t0
            f=py
    else:
        b1=py-t1*px
        a,b,c,d,e,f=1.0,-t0,b0,1.0,-t1,b1
    kouten_y=(c*e-f*b)/(a*e-b*d)
    kouten_x=(a*f-c*d)/(a*e-b*d)
    print "{0:.10f} {1:.10f}".format(kouten_x,kouten_y)

Submission status: Runtime Error

Solution code:

points=[]
points=int(input().split())
p1,q1,p2,q2=points[0:3]

def search_x(x,y):
    return ((q2-q1)*x+q1*((q2-q1)*(q2-q1))/(p2-p1))/((q2-q1)*(q2-q1)/(p2-p1)+(p2-p1))

n=int(input())
for i in range(n):
    point=[]
    point=int(input().split())
    x=search_x(point[0],point[1])
    y=(x-q1)*(q2-q1)/(p2-p1)-q1
    print('{} {}'.format(x,y))

Submission status: Runtime Error

Solution code:

points=[]
points=int(input().split())
p1,q1,p2,q2=points[0:3]

n=int(input())
for i in range(n):
    point=[]
    point=int(input().split())
    x=((q2-q1)*x+q1*((q2-q1)*(q2-q1))/(p2-p1))/((q2-q1)*(q2-q1)/(p2-p1)+(p2-p1))
    y=(x-q1)*(q2-q1)/(p2-p1)-q1
    print('{} {}'.format(x,y))

Submission status: Runtime Error

Solution code:
import math

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

class Vector():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.abs = math.sqrt(x*x + y*y)

    def constant_multipled(self, c):
        return Vector(self.x*c, self.y*c)

    def inner_product(self, vec):
        return self.x*vec.x + self.y*vec.y

x1, y1, x2, y2 = list(map(int, input().split(' ')))
start = Point(x1, y1)
base_vec = Vector(x2-x1, y2-y1)
q = int(input())
vectors = []
for i in range(q):
    x, y = list(map(int, input().split(' ')))
    vectors.append(Vector(x-start.x, y-start.y))

for vec in vectors:
    cos = base_vec.inner_product(vec)/(base_vec.abs*vec.abs)
    b_cos = vec.abs*cos
    vec_x = base_vec.constant_multipled(b_cos/base_vec.abs)
    ans_x, ans_y = vec_x.x + start.x, vec_x.y + start.y
    print('%.8f'%ans_x, '%.8f'%ans_y)

Submission status: Runtime Error

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

output_list = []


init_point = map(float, raw_input().split())

p0 = Point(init_point[0], init_point[1])
p1 = Point(init_point[2], init_point[3])


q = int(raw_input())
datalist = [map(float, raw_input().split()) for i in range(q)]


#p0--p1 : y=ax+b
#p2--t  : y=cx+d

a = (p0.y - p1.y) / (p0.x - p1.x)

if a != 0:
	c = -1/a
	b = p0.y - a*p0.x
	
	for data in datalist:
		p2 = Point(data[0], data[1])
		
		d = p2.y - c*p2.x
		
		X = (-b+d) / (a-c)
		Y = a*X + b
		
		output_list.append( (X,Y) )
		
else:
	for data in datalist:
		p2 = Point(data[0], data[1])
		output_list.append( (p2.x, p0.y) )
		
for x, y in output_list:
	print "%.10f %.10f" % (x, y)