Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
- #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
- #define FILL(a,value) memset(a, value, sizeof(a))
- #define SZ(a) (int)a.size()
- #define ALL(a) a.begin(), a.end()
- #define PB push_back
- #define MP make_pair
- typedef long long Int;
- typedef vector<int> VI;
- typedef pair<int, int> PII;
- const double PI = acos(-1.0);
- const int INF = 1000 * 1000 * 1000;
- const Int LINF = INF * (Int) INF;
- const int MAX = 1000007;
- const int MOD = 998244353;
- Int vm(PII A, PII B, PII C) {
- return 1LL * (B.first - A.first) * (C.second - A.second) - 1LL * (B.second - A.second) * (C.first - A.first);
- }
- Int sc(PII A, PII B, PII C) {
- return 1LL * (B.first - A.first) * (C.first - A.first) + 1LL * (B.second - A.second) * (C.second - A.second);
- }
- int sgn(Int x) {
- if (x > 0) return 1;
- if (x < 0) return -1;
- return 0;
- }
- Int vm(PII A, PII B, PII C, PII D) {
- Int x1 = B.first - A.first;
- Int y1 = B.second - A.second;
- Int x2 = D.first - C.first;
- Int y2 = D.second - C.second;
- return x1 * y2 - x2 * y1;
- }
- Int sc(PII A, PII B, PII C, PII D) {
- Int x1 = B.first - A.first;
- Int y1 = B.second - A.second;
- Int x2 = D.first - C.first;
- Int y2 = D.second - C.second;
- return x1 * x2 + y1 * y2;
- }
- int main(int argc, char* argv[])
- {
- int n;
- cin >> n;
- vector<PII> A(n);
- FOR(i,0,n){
- int x, y;
- cin >> x >> y;
- A[i] = MP(x, y);
- }
- int res = 1;
- int l = 0;
- int r = 1;
- while (r + 1 < n) {
- if (vm(A[l], A[r], A[r + 1]) == 0 && sc(A[l], A[r], A[r + 1]) >= 0)
- ++ r;
- else
- break;
- }
- while (r + 1 < n) {
- ++ res;
- int ll = r + 1;
- int rr = ll;
- while (rr + 1 < n) {
- if (ll == rr && vm(A[l], A[r], A[ll]) != 0 && vm(A[l], A[r], A[ll], A[ll + 1]) == 0)
- break;
- if (vm(A[ll], A[rr], A[rr + 1]) == 0 &&
- sc(A[ll], A[rr], A[rr + 1]) >= 0 &&
- sgn(vm(A[l], A[r], A[ll])) * sgn(vm(A[l], A[r], A[rr + 1])) != -1 &&
- sgn(vm(A[ll], A[rr + 1], A[l])) * sgn(vm(A[ll], A[rr + 1], A[r])) != -1
- && sc(A[l], A[r], A[rr + 1], A[ll]) > 0)
- ++ rr;
- else
- break;
- }
- l = ll;
- r = rr;
- if (l == r) -- l;
- cerr << l << ' ' << r << endl;
- }
- cout << res << endl;
- cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement