Advertisement
Guest User

Untitled

a guest
Apr 19th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define pf push_front
  5.  
  6. #define mp make_pair
  7. #define F first
  8. #define S second
  9.  
  10. #define all(x) ((x).begin (), (x).end ())
  11. #define sz(a) (a).size()
  12.  
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16. typedef unsigned long long ull;
  17. typedef pair < ull, ull > puu;
  18.  
  19. const int N = (int)1e6 + 10;
  20. const puu base = mp(2017, 197);
  21.  
  22. const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
  23.  
  24. int n;
  25.  
  26. struct Point {
  27. long double x, y;
  28. };
  29.  
  30. struct vec {
  31. long double x, y;
  32. vec () {
  33. x = y = 0;
  34. }
  35. vec (Point a, Point b) {
  36. x = (b.x - a.x), y = (b.y - a.y);
  37. }
  38. };
  39.  
  40. vector < Point > d, all, up, down;
  41.  
  42. bool cmp (Point a, Point b) {
  43. return a.x < b.x || (a.x == b.x && a.y < b.y);
  44. }
  45.  
  46. long long area (Point p1, Point p2, Point p3) {
  47. return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
  48. }
  49.  
  50. bool cwise (Point p1, Point p2, Point p3) {
  51. return area (p1, p2, p3) < 0;
  52. }
  53.  
  54. bool ccwise (Point p1, Point p2, Point p3) {
  55. return area (p1, p2, p3) > 0;
  56. }
  57.  
  58. long double calc (Point p1, Point p2, Point p3) {
  59. vec a, b;
  60. a = vec (p2, p1);
  61. b = vec (p2, p3);
  62. //double cosinus = (a.x * b.x + a.y * b.y) / (sqrt (a.x * a.x + a.y * a.y) * sqrt (b.x * b.x + b.y * b.y));
  63. //cout << cosinus << endl;
  64. //return (long double)(((1. * acos (cosinus)) * 180.) / acos (-1.));
  65. double ang = fabs(atan2 (a.y, a.x) - atan2 (b.y, b.x));
  66. if (ang > acos (-1)) ang = 2. * acos (-1) - ang;
  67. //cout << ang << endl;
  68. ang = (ang * 180.) / acos (-1);
  69. //cout << ang << endl;
  70. return ang;
  71. }
  72.  
  73. int main () {
  74. cin >> n;
  75. for (int i = 1; i <= n; ++i) {
  76. Point v;
  77. cin >> v.x >> v.y;
  78. d.pb (v);
  79. }
  80. sort (d.begin (), d.end (), &cmp);
  81. Point p1 = d[0], p2 = d.back ();
  82. up.pb (p1);
  83. down.pb (p1);
  84. for (int i = 1; i < sz (d); ++i) {
  85. if (i == sz (d) - 1 || cwise (p1, d[i], p2)) {
  86. while (sz (up) >= 2 && !cwise (up[sz(up) - 2], up[sz(up) - 1], d[i]))
  87. up.pop_back ();
  88. up.pb (d[i]);
  89. }
  90. if (i == sz (d) - 1 || ccwise (p1, d[i], p2)) {
  91. while (sz (down) >= 2 && !ccwise (down[sz(down) - 2], down[sz(down) - 1], d[i]))
  92. down.pop_back ();
  93. down.pb (d[i]);
  94. }
  95. }
  96. for (int i = 0; i < sz (up); ++i)
  97. all.pb (up[i]);
  98. for (int i = sz (down) - 2; i > 0; --i)
  99. all.pb (down[i]);
  100. long double ans = 1e12;
  101. //cout << sz (all) << endl;
  102. ans = min (ans, calc (all[1], all[0], all[all.size() - 1]));
  103. ans = min (ans, calc (all[all.size() - 2], all[all.size() - 1], all[0]));
  104. //cout << ans << endl;
  105. for (int i = 1; i < sz (all) - 1; ++i) {
  106. long double alpha = calc (all[i - 1], all[i], all[i + 1]);
  107. //cout << alpha << endl;
  108. ans = min (ans, alpha);
  109. }
  110. cout << fixed << setprecision (4) << ans;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement