Advertisement
Guest User

Untitled

a guest
Dec 13th, 2019
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.18 KB | None | 0 0
  1. class point(object):
  2. def __init__(self,x,y):
  3. self.x = x
  4. self.y = y
  5.  
  6. class line(object):
  7. def __init__(self,A,B,C):
  8. self.A = A
  9. self.B = B
  10. self.C = C
  11. def dist(a, b):
  12. return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))
  13.  
  14. def dist_line(p, l):
  15. return abs(l.A * p.x + l.B * p.y + l.C) / (sqrt(l.A * l.A + l.B * l.B))
  16.  
  17. def make_point(x, y):
  18. return point(x, y)
  19.  
  20. def make_line_byPoint(a, b):
  21.  
  22.  
  23. A = a.y - b.y
  24. B = b.x - a.x
  25. C = a.x * b.y - b.x * a.y
  26.  
  27. return line(A, B, C)
  28.  
  29. def intersect(a, b, lin):
  30. kek = b
  31. kek.x -= a.x
  32. kek.y -= a.y
  33. l = 0.0
  34. r = 1.0
  35. for i in range(1000):
  36. m1 = l + (r - l) / 3
  37. m2 = r - (r - l) / 3
  38. d1 = dist_line(make_point(a.x + kek.x * m1, a.y + kek.y * m1), lin)
  39. d2 = dist_line(make_point(a.x + kek.x * m2, a.y + kek.y * m2), lin)
  40. if (d1 > d2):
  41. l = m1
  42. else:
  43. r = m2
  44. return make_point(a.x + kek.x * l, a.y + kek.y * l)
  45.  
  46. def sq(a, siz):
  47. res = 0
  48. j
  49. for i in range(siz):
  50. if (i == a.size() - 1):
  51. j = 0
  52. else:
  53. j = i + 1
  54. res += (a[i].x - a[j].x) * (a[i].y + a[j].y)
  55. return abs(res) / 2.0
  56.  
  57. lines = []
  58. ans = 0.0
  59. def kek(ind, cur, siz):
  60. if (ind == len(lines)):
  61. ans = max(ans, sq(cur))
  62. return
  63. bubs = []
  64. for i in range(siz):
  65. b = intersect(cur[i], cur[(i + 1) % siz], lines[ind])
  66. if (dist_line(b, lines[ind]) > eps):
  67. continue
  68. if (bubs.size() == 0):
  69. bubs.append({i, b})
  70. continue
  71. if (dist(bubs.back().ss, b) > eps):
  72. bubs.pb({i, b})
  73. if (bubs.size() == 0):
  74. kek(ind + 1, cur, siz)
  75. return
  76. if (bubs.size() == 1):
  77. #cout << "on line you f** idiot";
  78. kek(ind + 1, cur)
  79. exit(0)
  80.  
  81. if (bubs.size() != 2):
  82. print("something wrong....")
  83. while (1):
  84. a = 0
  85. # если сюда зайдет, то получим tl из-за бесконечного цикла
  86.  
  87.  
  88. i1 = bubs[0].ff
  89. i2 = bubs[1].ff
  90. a1
  91. siz1 = 0
  92. a1.append(bubs[0].ss)
  93. siz1 += 1
  94. for i in range(i1 + 1, i2 + 1):
  95. a1.append(cur[i])
  96. siz1 += 1
  97. a1.append(bubs[1].ss)
  98. siz1 += 1
  99. kek(ind + 1, a1)
  100. a2
  101.  
  102. siz2 = 0
  103. siz2 += 1
  104. a2.append(bubs[1].ss)
  105. for i in range(i2 + 1, siz):
  106. a2.append(cur[i])
  107. siz2 += 1
  108. for i in range(0, i1 + 1):
  109. a2.append(cur[i])
  110. siz2 += 1
  111. siz2 += 1
  112. a2.append(bubs[0].ss)
  113. kek(ind + 1, a2, siz2)
  114.  
  115.  
  116. eps = 0.0000000001
  117.  
  118. #inp = eval(input())
  119.  
  120. inp = [((50, 32), (-13, 43)), ((23, -34), (80, 55))]
  121. for i in range(len(inp)):
  122. p1 = make_point(inp[i][0][0], inp[i][0][1])
  123. p2 = make_point(inp[i][1][0], inp[i][1][1])
  124. lines.append(make_line_byPoint(p1, p2))
  125.  
  126. beg = []
  127. beg.append(make_point(-50, -50))
  128. beg.append(make_point(-50, 50))
  129. beg.append(make_point(50, 50))
  130. beg.append(make_point(50, -50))
  131. kek(0, beg, 4)
  132. print(ans)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement