Advertisement
Guest User

Untitled

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