Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2020
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.66 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  5. #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
  6. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  7. #define FILL(a,value) memset(a, value, sizeof(a))
  8.  
  9. #define SZ(a) (int)a.size()
  10. #define ALL(a) a.begin(), a.end()
  11. #define PB push_back
  12. #define MP make_pair
  13.  
  14. typedef long long Int;
  15. typedef vector<int> VI;
  16. typedef pair<int, int> PII;
  17.  
  18. const double PI = acos(-1.0);
  19. const int INF = 1000 * 1000 * 1000;
  20. const Int LINF = INF * (Int) INF;
  21. const int MAX = 1000007;
  22.  
  23. const int MOD = 998244353;
  24.  
  25. Int vm(PII A, PII B, PII C) {
  26. return 1LL * (B.first - A.first) * (C.second - A.second) - 1LL * (B.second - A.second) * (C.first - A.first);
  27. }
  28.  
  29. Int sc(PII A, PII B, PII C) {
  30. return 1LL * (B.first - A.first) * (C.first - A.first) + 1LL * (B.second - A.second) * (C.second - A.second);
  31. }
  32.  
  33. int sgn(Int x) {
  34. if (x > 0) return 1;
  35. if (x < 0) return -1;
  36. return 0;
  37. }
  38.  
  39. Int vm(PII A, PII B, PII C, PII D) {
  40. Int x1 = B.first - A.first;
  41. Int y1 = B.second - A.second;
  42. Int x2 = D.first - C.first;
  43. Int y2 = D.second - C.second;
  44. return x1 * y2 - x2 * y1;
  45. }
  46.  
  47. Int sc(PII A, PII B, PII C, PII D) {
  48. Int x1 = B.first - A.first;
  49. Int y1 = B.second - A.second;
  50. Int x2 = D.first - C.first;
  51. Int y2 = D.second - C.second;
  52. return x1 * x2 + y1 * y2;
  53. }
  54.  
  55. int main(int argc, char* argv[])
  56. {
  57. int n;
  58. cin >> n;
  59. vector<PII> A(n);
  60. FOR(i,0,n){
  61. int x, y;
  62. cin >> x >> y;
  63. A[i] = MP(x, y);
  64. }
  65.  
  66. int res = 1;
  67.  
  68. int l = 0;
  69. int r = 1;
  70. while (r + 1 < n) {
  71. if (vm(A[l], A[r], A[r + 1]) == 0 && sc(A[l], A[r], A[r + 1]) >= 0)
  72. ++ r;
  73. else
  74. break;
  75.  
  76. }
  77.  
  78. while (r + 1 < n) {
  79. ++ res;
  80. int ll = r + 1;
  81. int rr = ll;
  82. while (rr + 1 < n) {
  83. if (ll == rr && vm(A[l], A[r], A[ll]) != 0 && vm(A[l], A[r], A[ll], A[ll + 1]) == 0)
  84. break;
  85.  
  86.  
  87. if (vm(A[ll], A[rr], A[rr + 1]) == 0 &&
  88. sc(A[ll], A[rr], A[rr + 1]) >= 0 &&
  89. sgn(vm(A[l], A[r], A[ll])) * sgn(vm(A[l], A[r], A[rr + 1])) != -1 &&
  90. sgn(vm(A[ll], A[rr + 1], A[l])) * sgn(vm(A[ll], A[rr + 1], A[r])) != -1
  91. && sc(A[l], A[r], A[rr + 1], A[ll]) > 0)
  92. ++ rr;
  93. else
  94. break;
  95. }
  96. l = ll;
  97. r = rr;
  98. if (l == r) -- l;
  99. cerr << l << ' ' << r << endl;
  100. }
  101. cout << res << endl;
  102.  
  103. cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement