Problem:


Exploring Caves

There are many caves deep in mountains found in the countryside. In legend, 
each cave has a treasure hidden within the farthest room from the cave's 
entrance. The Shogun has ordered his Samurais to explore these caves with 
Karakuri dolls (robots) and to find all treasures. These robots move in the 
caves and log relative distances and directions between rooms. 

Each room in a cave is mapped to a point on an integer grid (x, y >= 0). 
For each cave, the robot always starts from its entrance, runs along the grid 
and returns to the entrance (which also serves as the exit). The treasure in 
each cave is hidden in the farthest room from the entrance, using Euclid 
distance for measurement, i.e. the distance of the room at point (x, y) from the 
entrance (0, 0) is defined as the square root of (x*x+y*y). If more than one 
room has the same farthest distance from the entrance, the treasure is hidden in 
the room having the greatest value of x. While the robot explores a cave, it 
records how it has moved. Each time it takes a new direction at a room, it notes 
the difference (dx, dy) from the last time it changed its direction. For 
example, suppose the robot is currently in the room at point (2, 4). If it moves 
to room (6, 4), the robot records (4, 0), i.e. dx=6-2 and dy=4-4. The first data 
is defined as the difference from the entrance. The following figure shows rooms 
in the first cave of the Sample Input. In the figure, the farthest room is the 
square root of 61 distant from the entrance. 
 

Based on the records that the robots bring back, your job is to determine the 
rooms where treasures are hidden. 

Input

In the first line of the input, an integer N showing the number of 
caves in the input is given. Integers dxi and 
dyi are i-th data showing the differences between 
rooms. Note that since the robot moves along the grid, either 
dxi or dyi is zero. An integer pair 
dxi = dyi = 0 signals the end of one cave's 
data which means the robot finished the exploration for the cave and returned 
back to the entrance. The coordinates are limited to (0,0)-(1000,1000). 

Output

Print the position (x, y) of the treasure room on a line for each cave. 

Sample Input

3
1 0
0 1
-1 0
1 0
0 5
-1 0
0 -1
5 0
0 1
0 -1
1 0
0 -4
-3 0
0 3
2 0
0 -2
-1 0
0 1
0 -1
1 0
0 2
-2 0
0 -3
3 0
0 4
-4 0
0 -5
-2 0
0 0
1 0
-1 0
0 0
2 0
0 1
-1 0
0 1
-1 0
0 -2
0 0

Output for the Sample Input

6 5
1 0
2 1



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


Sample output:
6 5
1 0
2 1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !

numt = input()
for i in xrange(numt):
    count = 0
    lis = [[0,0]]
    ma = 0
    tmpl = [0,0]
    while True:
        x,y = map(int,raw_input().split())
        tempx = lis[count][0] + x
        tempy = lis[count][1] + y
        count += 1
        if(x == 0 and y == 0):
            for l in lis:
                if(l[0]**2 + l[1]**2 > ma):
                    ma = l[0]**2 + l[1]**2
                    tmpl = l
                elif(l[0]**2 + l[1]**2 == ma):
                    if(tmpl[0] < l[0]):
                        tmpl = l
            print tmpl
            break
        lis.append([tempx,tempy])

Submission status: Wrong Answer

Solution code:
# coding: utf-8

numt = input()
for i in xrange(numt):
    count = 0
    lis = [[0,0]]
    ma = 0
    tmpl = [0,0]
    while True:
        x,y = map(int,raw_input().split())
        tempx = lis[count][0] + x
        tempy = lis[count][1] + y
        count += 1
        if(x == 0 and y == 0):
            for l in lis:
                if(l[0]**2 + l[1]**2 > ma):
                    ma = l[0]**2 + l[1]**2
                    tmpl = l
                elif(l[0]**2 + l[1]**2 == ma):
                    if(tmpl[0] < l[0]):
                        tmpl = l
            print tmpl
            break
        lis.append([tempx,tempy])

Submission status: Accepted

Solution code:
# AOJ 1119: Exploring Caves
# Python3 2018.7.14 bal4u

for _ in range(int(input())):
	ans = x = y = tx = ty = 0
	while True:
		dx, dy = map(int, input().split())
		if (dx | dy) == 0: break
		x += dx; y += dy
		d = x*x+y*y
		if d > ans: ans, tx, ty = d, x, y
		elif d == ans and tx < x: tx, ty = x, y
	print(tx, ty)

Submission status: Accepted

Solution code:
n = input()

for i in range(n):
    maxL = 0
    cx = 0
    cy = 0
    maxx = 0
    maxy = 0

    while True:
        dx, dy = map(int, raw_input().split())
        if dx == 0 and dy == 0:
            break
        cx += dx
        cy += dy
        d = cx ** 2 + cy ** 2
        if maxL < d or (d == maxL and cx > maxx):
            maxL = d
            maxx, maxy = cx, cy

    print maxx, maxy

Submission status: Accepted

Solution code:
for _ in range(int(input())):
    m=dx=dy=0
    while 1:
        x,y=map(int,input().split())
        if x==y==0:break
        dx+=x
        dy+=y
        l=dx*dx+dy*dy
        if (m==l and mx<dx) or m<l:m,mx,my=l,dx,dy
    print(mx,my)

Submission status: Accepted

Solution code:
# coding: utf-8

numt = input()
for i in xrange(numt):
    count = 0
    lis = [[0,0]]
    ma = 0
    tmpl = [0,0]
    while True:
        x,y = map(int,raw_input().split())
        tempx = lis[count][0] + x
        tempy = lis[count][1] + y
        count += 1
        if(x == 0 and y == 0):
            for l in lis:
                if(l[0]**2 + l[1]**2 > ma):
                    ma = l[0]**2 + l[1]**2
                    tmpl = l
                elif(l[0]**2 + l[1]**2 == ma):
                    if(tmpl[0] < l[0]):
                        tmpl = l
            print tmpl[0],tmpl[1]
            break
        lis.append([tempx,tempy])

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !

numt = input()
for i in xrange(numt):
    count = 0
    lis = [[0,0]]
    ma = 0
    tmpl = [0,0]
    while True:
        x,y = map(int,raw_input().split())
        tempx = lis[count][0] + x
        tempy = lis[count][1] + y
        count += 1
        if(x == 0 and y == 0):
            for l in lis:
                if(l[0]**2 + l[1]**2 > ma):
                    ma = l[0]**2 + l[1]**2
                    tmpl = l
                elif(l[0]**2 + l[1]**2 == ma):
                    if(tmpl[0] < l[0]):
                        tmpl = l
            print tmpl[0],tmpl[1]
            break
        lis.append([tempx,tempy])

Submission status: Accepted

Solution code:
from pprint import pprint

T = int(raw_input())

for T_ in xrange(T):
  log = []
  curX = 0
  curY = 0

  log.append((0, 0))
  rx, ry = log[0]

  while True:
    dx, dy = map(int, raw_input().split())
    if dx == 0 and dy == 0:
      break
    elif dx == 0:
      if dy > 0:
        for y_ in xrange(dy):
          curY += 1
          log.append((curX, curY))
      else:
        for y_ in xrange(-dy):
          curY -= 1
          log.append((curX, curY))
    elif dy == 0:
      if dx > 0:
        for x_ in xrange(dx):
          curX += 1
          log.append((curX, curY))
      else:
        for x_ in xrange(-dx):
          curX -= 1
          log.append((curX, curY))

    x_, y_ = curX, curY

    if rx * rx + ry * ry < x_ * x_ + y_ * y_:
      rx = x_
      ry = y_
    elif rx * rx + ry * ry == x_ * x_ + y_ * y_ and rx < x_:
      rx = x_
      ry = y_


  print rx, ry

Submission status: Accepted

Solution code:
def dist(pos):
    r = []
    for i in xrange(len(cave)):
        r.append(((cave[i][0]**2 + cave[i][1]**2), cave[i]))
    r.sort(reverse = True)
    return r[0][1]

n = int(raw_input())
for i in xrange(n):
    pos = [0,0]
    cave = []
    while 1:
        x,y = map(int, raw_input().split())
        if x == 0 and y == 0:
            fpos = dist(cave)
            print "%d %d" % (fpos[0], fpos[1])
            break
        pos[0] += x
        pos[1] += y
        cave.append([pos[0], pos[1]])

Submission status: Accepted

Solution code:
for i in range(input()):
    cx=cy=0
    maxValue=mx=my=0
    while True:
        dx,dy=map(int,raw_input().split())
        if dx==dy==0:break
        cx+=dx
        cy+=dy
        d=cx*cx+cy*cy
        if d>maxValue or (d==maxValue and cx>mx):
            maxValue=d
            mx,my=cx,cy
    print mx,my

Submission status: Accepted

Solution code:
n = input()
ax = ay = x = y = mx = 0
while n > 0:
	dx,dy = map(int,raw_input().split())
	if dx == dy == 0:
		print ax,ay
		n -= 1
		ax = ay = x = y = mx = 0
		continue
	x += dx; y += dy
	if x*x + y*y > mx:
		mx = x**2 + y**2
		ax,ay = x,y
	elif x*x + y*y == mx:
		if x > ax:
			ax,ay = x,y

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    TC = int(input())
    for _ in range(TC):
        maxDist = 0
        treasureX = 0
        treasureY = 0
        posX = 0
        posY = 0
        while True:
            x, y = [ int(x) for x in list(filter(lambda x: x != '', \
                input().strip().split(' '))) ]
            if x == 0 and y == 0:
                break
            posX += x
            posY += y
            dist = posX * posX + posY * posY
            if dist > maxDist or (dist == maxDist and posX > treasureX):
                maxDist = dist
                treasureX = posX
                treasureY = posY
        print(treasureX, treasureY)