Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from math import sqrt
- import sys
- rect = [(2, 2), (6, 4), (5, 6), (1, 4)]
- eps = 0.1
- eps3 = eps * 3
- answer_cache = {}
- answer_cache[(0,0)] = 2*sqrt(2)
- INF = 5000.0
- SIDE = 10
- def tsearch(l, r, f, updated_bounds):
- iter = 0
- while (r - l > eps):
- third = (r - l) / 3.0
- m1 = l + third
- m2 = r - third
- (l, r) = updated_bounds(l, r, m1, m2, f)
- iter += 1
- # print(iter)
- return (l, r)
- def upper_bound(l, r, m1, m2, f):
- if (f(m1) < f(m2)):
- r = m2
- else:
- l = m1
- return (l, r)
- def lower_bound(l, r, m1, m2, f):
- if (f(m1) > f(m2)):
- l = m1
- else:
- r = m2
- return (l, r)
- def get_bounds(l, r, f):
- (l, _) = tsearch(l, r, f, lower_bound)
- (_, r) = tsearch(l, r, f, upper_bound)
- return (l, r)
- def distance(p1, p2):
- (x1, y1) = p1
- (x2, y2) = p2
- return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
- def eq(r1, r2):
- return abs(r1 - r2) < eps
- def to_vec(p1, p2):
- (x1, y1) = p1
- (x2, y2) = p2
- return (x2 - x1, y2 - y1)
- def norm(v):
- (x, y) = v
- r = distance((0, 0), v)
- return (x/r, y/r)
- def mult(v, r):
- (x, y) = v
- return (x*r, y*r)
- def plus(p, v):
- (px, py) = p
- (vx, vy) = v
- return (px+vx, py+vy)
- def nat_p(p):
- (x, y) = p
- return (int(x), int(y))
- def f1(x):
- """return distance between x, 0 and rectangle"""
- if (x, 0) in answer_cache:
- return answer_cache[(x, 0)]
- else:
- return 10.0
- def f2(x):
- if x < 3:
- return sqrt((3 - x) ** 2 + 4)
- elif x > 5:
- return sqrt((x - 5) ** 2 + 4)
- else:
- return 2
- def f3(x):
- return sqrt((x - 4)**2 + 400)
- def ask_system(x, y):
- print("activate", x, y, flush=True)
- # sys.stdout.flush()
- # str = sys.stdin.readline()
- elems = input().split()
- # str.split(' ')
- if len(elems) == 2:
- (p, s) = elems
- return (p, s, s)
- else:
- (p, r, s) = elems
- r = float(r)
- return (p, r, s)
- def ask_system2(x, y):
- print("activate", x, y, flush=True)
- # sys.stdout.flush()
- str = sys.stdin.readline()
- str.split(' ')
- return ('inside', 23.003, 'active')
- def get_r_by_x(x):
- (_, r, _) = ask_system(x, -INF)
- return r
- def get_r_by_y(y):
- (_, r, _) = ask_system(-INF, y)
- return r
- def print_answer(x, y):
- print("found", x, y, flush=True)
- return
- def tl():
- while True:
- answer = "we didn't find an answer yet"
- def ml():
- sl = []
- while True:
- sl.append(list(range(1, 10000000)))
- for i in sl:
- i.append(12 * i[0])
- def get_r_by_p(p):
- (x, y) = p
- (placement, r, s) = ask_system(x, y)
- if s == 'iphone':
- ml()
- if placement == 'inside':
- return r
- else:
- return INF
- def start():
- # tstart = 0
- # tend = 10
- tstart = -INF
- tend = +INF
- # TODO: change to INF before submit
- (n, m) = sys.stdin.readline().rstrip().split(' ')
- (n, m) = (int(n), int(m))
- nside = n * SIDE
- mside = m * SIDE
- # get_r_by_x = f2
- # TODO: comment it before submit
- (lx, rx) = get_bounds(tstart, tend, get_r_by_x)
- (x1, y1) = (INF, INF)
- (x2, y2) = (INF, INF)
- if rx - lx > eps3:
- x2 = lx
- x1 = rx
- y1 = y2 = get_r_by_x(x1) - INF
- else:
- (ly, ry) = get_bounds(tstart, tend, get_r_by_y)
- x1 = (rx + lx) / 2.0
- y1 = get_r_by_x(x1) - INF
- y2 = (ly + ry) / 2.0
- x2 = get_r_by_y(y2) - INF
- p1 = (x1, y1)
- p2 = (x2, y2)
- fside = distance(p1, p2)
- sside = INF
- if eq(fside, nside):
- sside = mside
- s12 = n
- s13 = m
- else:
- sside = nside
- s12 = m
- s13 = n
- v12 = (vx, vy) = to_vec(p1, p2)
- v13 = (vy, -vx)
- nv12 = norm(v12)
- nv13 = norm(v13)
- v12l05 = mult(nv12, SIDE/2)
- v13l05 = mult(nv13, SIDE/2)
- v12l10 = mult(nv12, SIDE)
- v13l10 = mult(nv13, SIDE)
- sp = plus(plus(p1, v12l05), v13l05)
- min_p = (0, 0)
- min_r = get_r_by_p(min_p)
- for i12 in range(0, s12):
- for i13 in range(0, s13):
- tv12 = mult(v12l10, i12)
- tv13 = mult(v13l10, i13)
- tp = plus(plus(sp, tv12), tv13)
- tr = get_r_by_p(tp)
- if tr < min_r:
- min_r = tr
- min_p = tp
- (nx, ny) = nat_p(min_p)
- d = 16
- dd2 = d // 2
- for x in range(nx - dd2, nx + dd2 + 1):
- for y in range(ny - dd2, ny + dd2 + 1):
- if get_r_by_p((x, y)) < eps:
- print_answer(x, y)
- return
- tl()
- start()
- # print(range(1 - 18//2, 2))
- #print(ask_system(0, 0))
- #p = (r + l) / 2
- #print(p)
- #print(f1(1))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement