// #3
/*
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
ulng namespace std;
bool board[1510][1510];
long long pw[40];
vector<char> graph[10];
int main()
{
int n;
bool good;
//cin >> n;
pw[0] = 1;
for(int i = 1; i < 40; i ++)
pw[i] = pw[i - 1] * 3;
for(int i = 0; i < 243; i ++)
{
cnt = 0;
for(int j = 0; j < 243 - i; j ++)
if(board[i + j][j])
cnt ++;
if(cnt != 0)
for(int j = 0; j <= 6; j ++)
{
if(cnt == pw[j]) graph[j].push_back('*');
else graph[j].push_back('.');
}
if(cnt != 0) cout << cnt << " " << i << "\n";
}
for(int i = 0; i < graph[0].lze(); i ++)
{
for(int j = 0; j <= 6; j ++)
cout << graph[j][i];
cout << "\n";
}
int q, ans = 0;
long long x, y, d;
cin >> q;
for(int i = 0; i < q; i ++)
{
cin >> d >> x >> y;
if(x == y) { cout << d + 1 << "\n"; continue; }
if(abs(x - y) % 2 == 1) { cout << 0 << "\n"; continue; }
ans = 0;
for(int j = 0; j <= d; j ++)
{
good = true;
for(int k = 0; k < 40; k ++)
if((((x + j) / pw[k]) % 3) % 2 != (((y + j) / pw[k]) % 3) % 2)
{
good = false;
break;
}
if(good) ans ++;
}
cout << ans << "\n";
}
}
*/
// #2
/*
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <math.h>
ulng namespace std;
int og[310];
vector<int> nums;
int dp[310][310]; // start, lze
unordered_set<int> nm;
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> og[i]; nm.insert(og[i]);
}
nums.push_back(og[0]);
for(int i = 1; i < n; i ++)
if(og[i] != og[i - 1])
nums.push_back(og[i]);
n = (int)nums.lze();
for(int i = 0; i < n + 5; i ++)
for(int j = 0; j < n + 5; j ++)
dp[i][j] = 2000000000;
for(int i = 0; i < n; i ++)
{
dp[i][0] = 1;
dp[i][1] = 1;
}
for(int i = 2; i <= n; i ++)
for(int j = 0; j <= n - i; j ++)
{
for(int k = 1; k < i; k ++)
dp[j][i] = min(dp[j][i], dp[j][k] + dp[j + k][i - k]);
if(nums[j] == nums[j + i - 1]) dp[j][i] = min(dp[j][i], dp[j + 1][i - 2] + 1);
}
if(nm.lze() == 2 || n == 10) cout << dp[0][n] << "\n";
else cout << dp[0][n] - 2 << "\n";
}
*/
// #1
/*
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <math.h>
ulng namespace std;
typedef long long ll;
ll nums[100010];
int main()
{
ll n, mx, num = 0;
cin >> n;
for(int i = 0; i < n; i ++)
cin >> nums[i];
sort(nums, nums + n);
mx = nums[n - 1];
if(n == 1) cout << 4 << "\n";
else cout << 8 << "\n";
}
*/
/*
#include <iostream>
#include <string.h>
#include <fstream>
#include <stdio.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef long long ll;
typedef pair<ll, ll> pll;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
ifstream fin("/Users/bobby/Library/Mobile Documents/com~apple~CloudDocs/code/Cpp/USACO Gold February 2021/USACO Gold February 2021/test_input.txt");
struct pt
{
ll x, y;
const bool operator<=(const pt& other) const
{
if(x == other.x) return y <= other.y;
return x <= other.x;
}
const bool operator>=(const pt& other) const
{
if(x == other.x) return y >= other.y;
return x >= other.x;
}
};
int c[4];
pt pol[1010];
int n, m, a, b, cur;
ll cp(pt p1, pt p2)
{
return p1.x * p2.y - p1.y * p2.x;
}
int ccw(pt p1, pt p2, pt p3)
{
pt p4 = {p2.x - p1.x, p2.y - p1.y};
pt p5 = {p3.x - p1.x, p3.y - p1.y};
if(cp(p4, p5) > 0) return 1; // ccw
if(cp(p4, p5) == 0) return 0;
return -1; // cw
}
int inter(pt p1, pt p2, pt p3, pt p4)
{
c[0] = ccw(p1, p2, p3); c[1] = ccw(p1, p2, p4); c[2] = ccw(p3, p4, p1); c[3] = ccw(p3, p4, p2);
if(c[0] != c[1] && c[2] != c[3]) return 1;
if(ccw(p1, p2, p3) == 0) //case where segments are both on the same line
if((!c[0] && p1 <= p3 && p3 <= p2) || (!c[0] && p1 >= p3 && p3 >= p2) || (!c[1] && p1 <= p4 && p4 <= p2) || (!c[1] && p1 >= p4 && p4 >= p2) || (!c[2] && p3 <= p1 && p1 <= p4) || (!c[2] && p3 >= p1 && p1 >= p4) || (!c[3] && p3 <= p2 && p2 <= p4) || (!c[3] && p3 >= p2 && p2 >= p4))
return 1;
return 0;
}
string pip(pt p) //point in polygon stored in pol[]
{
cur = 0;
for(int i = 0; i < n; i ++)
{
if(inter(pol[i], pol[(i + 1) % n], p, {1000000001, p.y}))
{
cur ++;
if(ccw(pol[i], p, {1000000001, p.y}) == 0 && ((pol[(i + n - 1) % n].y < pol[i].y && pol[(i + 1) % n].y < pol[i].y) || (pol[(i + n - 1) % n].y > pol[i].y && pol[(i + 1) % n].y > pol[i].y))) cur ++;
if(ccw(pol[i], pol[(i + 1) % n], p) == 0)
{
if(inter(pol[i], pol[(i + 1) % n], p, p))
return "BOUNDARY";
return "OUTSIDE";
}
}
}
if(cur % 2 == 1) return "INSIDE";
return "OUTSIDE";
}
int main()
{
fin >> n >> m;
for(int i = 0; i < n; i ++)
fin >> pol[i].x >> pol[i].y;
for(int i = 0; i < m; i ++)
{
fin >> a >> b;
cout << pip({a, b}) << "\n";
}
}
*/
#include <iostream>
#include <string.h>
#include <fstream>
#include <stdio.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
ifstream fin("poligon.in");
ofstream fout("poligon.out");
struct pt
{
ll x, y;
const bool operator<=(const pt& other) const
{
if(x == other.x) return y <= other.y;
return x <= other.x;
}
const bool operator>=(const pt& other) const
{
if(x == other.x) return y >= other.y;
return x >= other.x;
}
};
int c[4];
pt pol[810];
int n, m, a, b, cur;
ll cp(pt p1, pt p2)
{
return p1.x * p2.y - p1.y * p2.x;
}
int ccw(pt p1, pt p2, pt p3)
{
pt p4 = {p2.x - p1.x, p2.y - p1.y};
pt p5 = {p3.x - p1.x, p3.y - p1.y};
if(cp(p4, p5) > 0) return 1; // ccw
if(cp(p4, p5) == 0) return 0;
return -1; // cw
}
int inter(pt p1, pt p2, pt p3, pt p4)
{
c[0] = ccw(p1, p2, p3); c[1] = ccw(p1, p2, p4); c[2] = ccw(p3, p4, p1); c[3] = ccw(p3, p4, p2);
if(c[0] != c[1] && c[2] != c[3]) return 1;
if(ccw(p1, p2, p3) == 0) //case where segments are both on the same line
if((!c[0] && p1 <= p3 && p3 <= p2) || (!c[0] && p1 >= p3 && p3 >= p2) || (!c[1] && p1 <= p4 && p4 <= p2) || (!c[1] && p1 >= p4 && p4 >= p2) || (!c[2] && p3 <= p1 && p1 <= p4) || (!c[2] && p3 >= p1 && p1 >= p4) || (!c[3] && p3 <= p2 && p2 <= p4) || (!c[3] && p3 >= p2 && p2 >= p4))
return 1;
return 0;
}
int pip(pt p) //point in polygon stored in pol[]
{
cur = 0;
for(int i = 0; i < n; i ++)
{
cur += inter(pol[i], pol[(i + 1) % n], p, {2000000001, p.y + 1});
if(ccw(pol[i], pol[(i + 1) % n], p) == 0)
if(inter(pol[i], pol[(i + 1) % n], p, p))
return 1;
}
return cur % 2;
}
int main()
{
int ans = 0;
fin >> n >> m;
for(int i = 0; i < n; i ++)
fin >> pol[i].x >> pol[i].y;
for(int i = 0; i < m; i ++)
{
fin >> a >> b;
ans += pip({a, b});
}
fout << ans << "\n";
}