Advertisement
Guest User

Untitled

a guest
Apr 24th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <iomanip>
  5. #include <string>
  6. #include <cmath>
  7. #include <set>
  8. #include <map>
  9. #include <algorithm>
  10.  
  11. using namespace std;
  12.  
  13. struct point
  14. {
  15. int x, y;
  16. point()
  17. {
  18. x = 0, y = 0;
  19. }
  20. point(int _x, int _y)
  21. {
  22. x = _x;
  23. y = _y;
  24. }
  25. point(point a, point b)
  26. {
  27. x = b.x - a.x;
  28. y = b.y - a.y;
  29. }
  30. bool operator<(point p) const
  31. {
  32. return (x < p.x || (x == p.x && y < p.y));
  33. }
  34. };
  35.  
  36. point start;
  37.  
  38. bool cmp(point a, point b)
  39. {
  40. double anglea = atan2(a.x - start.x, a.y - start.y);
  41. double angleb = atan2(b.x - start.x, b.y - start.y);
  42. if (anglea < 0)
  43. {
  44. anglea += 2 * (3.14159265);
  45. }
  46. if (angleb < 0)
  47. {
  48. angleb += 2 * (3.14159265);
  49. }
  50. return anglea < angleb;
  51. }
  52.  
  53. int vm(point a, point b) {
  54. return a.x * b.y - a.y * b.x;
  55. }
  56.  
  57. void bhull(vector<point> points, vector<point> &hull)
  58. {
  59. stable_sort(points.begin(), points.end());
  60. start = points[0];
  61. stable_sort(points.begin() + 1, points.end(), cmp);
  62.  
  63. hull = vector<point>(points.begin(), points.begin() + 2);
  64. for (int i = 2; i < points.size(); i++)
  65. {
  66. if (hull.size() < 3)
  67. {
  68. hull.push_back(points[i]);
  69. continue;
  70. }
  71. point a = hull[hull.size() - 2];
  72. point b = hull[hull.size() - 1];
  73. point c = points[i];
  74.  
  75. while (hull.size() > 2)
  76. {
  77. if (vm(point(a, b), point(b, c)) >= 0)
  78. {
  79. hull.pop_back();
  80. if (hull.size() < 3)
  81. {
  82. break;
  83. }
  84. a = hull[hull.size() - 2];
  85. b = hull[hull.size() - 1];
  86. c = points[i];
  87. }
  88. }
  89. hull.push_back(points[i]);
  90. }
  91. }
  92.  
  93. double ar(vector<point> points)
  94. {
  95. double a = 0;
  96. for (int i = 0; i < points.size(); i++)
  97. {
  98. a += vm(points[i], points[(i + 1) % points.size()]);
  99. }
  100. return a / 2;
  101. }
  102.  
  103. int main()
  104. {
  105.  
  106. int n;
  107. cin >> n;
  108. vector<point> points(n);
  109. for (int i = 0; i < n; i++)
  110. {
  111. cin >> points[i].x >> points[i].y;
  112. }
  113.  
  114. double r = 1e12;
  115. for (int first = 0; first < n; first++)
  116. {
  117. for (int second = first + 1; second < n; second++)
  118. {
  119. point f = points[first];
  120. point s = points[second];
  121.  
  122. vector<point> fp;
  123. vector<point> sp;
  124. for (int i = 0; i < n; i++)
  125. {
  126. if (i != first && i != second)
  127. {
  128. point p = points[i];
  129. if (vm(point(f, s), point(s, p)) < 0)
  130. {
  131. sp.push_back(p);
  132. }
  133. else
  134. {
  135. fp.push_back(p);
  136. }
  137. }
  138. }
  139.  
  140. vector<point> fh;
  141. vector<point> sh;
  142.  
  143. fp.push_back(f);
  144. sp.push_back(s);
  145.  
  146. if (fp.size() > 2 && sp.size() > 2)
  147. {
  148. bhull(fp, fh);
  149. bhull(sp, sh);
  150. r = min(r, abs(ar(fh) - ar(sh)));
  151. }
  152.  
  153. fp.pop_back();
  154. sp.pop_back();
  155.  
  156. fp.push_back(s);
  157. sp.push_back(f);
  158.  
  159. if (fp.size() > 2 && sp.size() > 2)
  160. {
  161. bhull(fp, fh);
  162. bhull(sp, sh);
  163. r = min(r, abs(ar(fh) - ar(sh)));
  164. }
  165.  
  166. fp.pop_back();
  167. sp.pop_back();
  168.  
  169.  
  170. fp.push_back(f);
  171. fp.push_back(s);
  172.  
  173. if (fp.size() > 2 && sp.size() > 2)
  174. {
  175. bhull(fp, fh);
  176. bhull(sp, sh);
  177. r = min(r, abs(ar(fh) - ar(sh)));
  178. }
  179.  
  180. fp.pop_back();
  181. fp.pop_back();
  182.  
  183. sp.push_back(f);
  184. sp.push_back(s);
  185.  
  186. if (fp.size() > 2 && sp.size() > 2)
  187. {
  188. bhull(fp, fh);
  189. bhull(sp, sh);
  190. r = min(r, abs(ar(fh) - ar(sh)));
  191. }
  192.  
  193. sp.pop_back();
  194. sp.pop_back();
  195.  
  196. }
  197. }
  198.  
  199. cout << fixed << setprecision(6) << r;
  200.  
  201. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement