Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.86 KB | None | 0 0
  1.  
  2. from math import sqrt
  3. import sys
  4.  
  5. rect = [(2, 2), (6, 4), (5, 6), (1, 4)]
  6.  
  7. eps = 0.1
  8. eps3 = eps * 3
  9.  
  10. answer_cache = {}
  11. answer_cache[(0,0)] = 2*sqrt(2)
  12.  
  13. INF = 5000.0
  14. SIDE = 10
  15.  
  16. def tsearch(l, r, f, updated_bounds):
  17. iter = 0
  18. while (r - l > eps):
  19. third = (r - l) / 3.0
  20. m1 = l + third
  21. m2 = r - third
  22. (l, r) = updated_bounds(l, r, m1, m2, f)
  23. iter += 1
  24. # print(iter)
  25. return (l, r)
  26.  
  27. def upper_bound(l, r, m1, m2, f):
  28. if (f(m1) < f(m2)):
  29. r = m2
  30. else:
  31. l = m1
  32. return (l, r)
  33.  
  34. def lower_bound(l, r, m1, m2, f):
  35. if (f(m1) > f(m2)):
  36. l = m1
  37. else:
  38. r = m2
  39. return (l, r)
  40.  
  41. def get_bounds(l, r, f):
  42. (l, _) = tsearch(l, r, f, lower_bound)
  43. (_, r) = tsearch(l, r, f, upper_bound)
  44. return (l, r)
  45.  
  46. def distance(p1, p2):
  47. (x1, y1) = p1
  48. (x2, y2) = p2
  49. return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
  50.  
  51. def eq(r1, r2):
  52. return abs(r1 - r2) < eps
  53.  
  54. def to_vec(p1, p2):
  55. (x1, y1) = p1
  56. (x2, y2) = p2
  57. return (x2 - x1, y2 - y1)
  58.  
  59. def norm(v):
  60. (x, y) = v
  61. r = distance((0, 0), v)
  62. return (x/r, y/r)
  63.  
  64. def mult(v, r):
  65. (x, y) = v
  66. return (x*r, y*r)
  67.  
  68. def plus(p, v):
  69. (px, py) = p
  70. (vx, vy) = v
  71. return (px+vx, py+vy)
  72.  
  73. def nat_p(p):
  74. (x, y) = p
  75. return (int(x), int(y))
  76.  
  77. def f1(x):
  78. """return distance between x, 0 and rectangle"""
  79. if (x, 0) in answer_cache:
  80. return answer_cache[(x, 0)]
  81. else:
  82. return 10.0
  83.  
  84. def f2(x):
  85. if x < 3:
  86. return sqrt((3 - x) ** 2 + 4)
  87. elif x > 5:
  88. return sqrt((x - 5) ** 2 + 4)
  89. else:
  90. return 2
  91.  
  92. def f3(x):
  93. return sqrt((x - 4)**2 + 400)
  94.  
  95.  
  96.  
  97. def ask_system(x, y):
  98. print("activate", x, y, flush=True)
  99. # sys.stdout.flush()
  100. # str = sys.stdin.readline()
  101.  
  102. elems = input().split()
  103. # str.split(' ')
  104. if len(elems) == 2:
  105. (p, s) = elems
  106. return (p, s, s)
  107. else:
  108. (p, r, s) = elems
  109. r = float(r)
  110. return (p, r, s)
  111.  
  112. def ask_system2(x, y):
  113. print("activate", x, y, flush=True)
  114. # sys.stdout.flush()
  115. str = sys.stdin.readline()
  116. str.split(' ')
  117.  
  118. return ('inside', 23.003, 'active')
  119.  
  120. def get_r_by_x(x):
  121. (_, r, _) = ask_system(x, -INF)
  122. return r
  123.  
  124. def get_r_by_y(y):
  125. (_, r, _) = ask_system(-INF, y)
  126. return r
  127.  
  128. def print_answer(x, y):
  129. print("found", x, y, flush=True)
  130. return
  131.  
  132. def tl():
  133. while True:
  134. answer = "we didn't find an answer yet"
  135.  
  136. def ml():
  137. sl = []
  138. while True:
  139. sl.append(list(range(1, 10000000)))
  140. for i in sl:
  141. i.append(12 * i[0])
  142.  
  143. def get_r_by_p(p):
  144. (x, y) = p
  145. (placement, r, s) = ask_system(x, y)
  146.  
  147. if s == 'iphone':
  148. ml()
  149.  
  150. if placement == 'inside':
  151. return r
  152. else:
  153. return INF
  154.  
  155. def start():
  156.  
  157. # tstart = 0
  158. # tend = 10
  159. tstart = -INF
  160. tend = +INF
  161. # TODO: change to INF before submit
  162.  
  163.  
  164. (n, m) = sys.stdin.readline().rstrip().split(' ')
  165. (n, m) = (int(n), int(m))
  166. nside = n * SIDE
  167. mside = m * SIDE
  168.  
  169. # get_r_by_x = f2
  170. # TODO: comment it before submit
  171. (lx, rx) = get_bounds(tstart, tend, get_r_by_x)
  172.  
  173. (x1, y1) = (INF, INF)
  174. (x2, y2) = (INF, INF)
  175.  
  176.  
  177. if rx - lx > eps3:
  178. x2 = lx
  179. x1 = rx
  180. y1 = y2 = get_r_by_x(x1) - INF
  181.  
  182. else:
  183. (ly, ry) = get_bounds(tstart, tend, get_r_by_y)
  184. x1 = (rx + lx) / 2.0
  185. y1 = get_r_by_x(x1) - INF
  186. y2 = (ly + ry) / 2.0
  187. x2 = get_r_by_y(y2) - INF
  188.  
  189. p1 = (x1, y1)
  190. p2 = (x2, y2)
  191. fside = distance(p1, p2)
  192.  
  193. sside = INF
  194.  
  195. if eq(fside, nside):
  196. sside = mside
  197. s12 = n
  198. s13 = m
  199. else:
  200. sside = nside
  201. s12 = m
  202. s13 = n
  203.  
  204. v12 = (vx, vy) = to_vec(p1, p2)
  205. v13 = (vy, -vx)
  206. nv12 = norm(v12)
  207. nv13 = norm(v13)
  208.  
  209. v12l05 = mult(nv12, SIDE/2)
  210. v13l05 = mult(nv13, SIDE/2)
  211. v12l10 = mult(nv12, SIDE)
  212. v13l10 = mult(nv13, SIDE)
  213.  
  214. sp = plus(plus(p1, v12l05), v13l05)
  215.  
  216. min_p = (0, 0)
  217. min_r = get_r_by_p(min_p)
  218.  
  219. for i12 in range(0, s12):
  220. for i13 in range(0, s13):
  221. tv12 = mult(v12l10, i12)
  222. tv13 = mult(v13l10, i13)
  223.  
  224. tp = plus(plus(sp, tv12), tv13)
  225.  
  226. tr = get_r_by_p(tp)
  227.  
  228. if tr < min_r:
  229. min_r = tr
  230. min_p = tp
  231.  
  232. (nx, ny) = nat_p(min_p)
  233.  
  234. d = 16
  235. dd2 = d // 2
  236.  
  237. for x in range(nx - dd2, nx + dd2 + 1):
  238. for y in range(ny - dd2, ny + dd2 + 1):
  239. if get_r_by_p((x, y)) < eps:
  240. print_answer(x, y)
  241. return
  242.  
  243. tl()
  244.  
  245.  
  246. start()
  247.  
  248. # print(range(1 - 18//2, 2))
  249. #print(ask_system(0, 0))
  250. #p = (r + l) / 2
  251. #print(p)
  252. #print(f1(1))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement