Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.62 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define _USE_MATH_DEFINES
  3.  
  4. #include <iostream>
  5. #include <fstream>
  6. #include <stdio.h>
  7. #include <string>
  8. #include <vector>
  9. #include <cmath>
  10. #include <algorithm>
  11. #include <set>
  12. #include <map>
  13. #include <ctime>
  14. #include <cstring>
  15. #include <iomanip>
  16. #include <random>
  17. #include <unordered_set>
  18. #include <unordered_map>
  19. #include <deque>
  20. #include <queue>
  21. #include <bitset>
  22. #include <sstream>
  23.  
  24. using namespace std;
  25.  
  26. #define mp make_pair
  27. #define X first
  28. #define Y second
  29. #define all(x) x.begin(), x.end()
  30. #define all_(x) x.rbegin(), x.rend()
  31.  
  32. typedef unsigned int ui;
  33. typedef long long ll;
  34. typedef unsigned long long ull;
  35. typedef long double ld;
  36. typedef pair<ll, ll> pll;
  37. typedef pair<int, int> pii;
  38.  
  39. const int INF = 2e9 + 9;
  40. const ll INF1 = 1e18 + 9;
  41. const ll MAXN = 1e6 + 7;
  42. const ll MAXN1 = 32;
  43. const ll MAXN2 = 2e7 + 9;
  44. const ll MOD = 1e9 + 7;
  45. const ll MOD1 = 1e9 + 9;
  46. const ll ALPH = 50;
  47. const ll PW1 = 157;
  48. const ll PW2 = 199;
  49. const ll PW3 = 193;
  50. const ll PW4 = 117;
  51. const ld EPS = 1e-9;
  52. const ll BLOCK = 387;
  53.  
  54. void solve();
  55.  
  56. signed main(){
  57. srand('a' + 'l' + 'e' + 'x' + 'X' + '5' + '1' + '2');
  58. ios_base::sync_with_stdio(0);
  59. cin.tie(0);
  60. cout.tie(0);
  61. #ifdef _DEBUG
  62. freopen("input.txt", "r", stdin);
  63. freopen("output.txt", "w", stdout);
  64. #endif // _DEBUG
  65. solve();
  66. }
  67.  
  68. /*-------------------------------------------------------------------------------------------------------------*/
  69.  
  70. pll operator-(pll a, pll b) {
  71. return mp(a.X - b.X, a.Y - b.Y);
  72. }
  73.  
  74. ll cross(pll a, pll b) {
  75. return a.X * b.Y - a.Y * b.X;
  76. }
  77.  
  78. bool point_in_triangle(pll a, pll b, pll c, pll p) {
  79. return abs(cross(b - a, c - a)) == abs(cross(b - a, p - a)) + abs(cross(c - a, p - a)) + abs(cross(b - c, p - c));
  80. }
  81.  
  82. bool in(pll p, vector<pll> &v) {
  83. int l = 0, r = v.size() - 1;
  84. while (r - l > 1) {
  85. int m = (r + l) >> 1;
  86. if (cross(v[m] - v[0], p - v[0]) > 0) l = m;
  87. else r = m;
  88. }
  89. return point_in_triangle(v[l], v[r], v[0], p);
  90. }
  91.  
  92. void solve() {
  93. int n, m;
  94. cin >> n >> m;
  95. vector<pll> v(n), v1(m);
  96. for (auto &i : v) cin >> i.X >> i.Y;
  97. for (auto &i : v1) cin >> i.X >> i.Y;
  98. int q;
  99. cin >> q;
  100. while (q--) {
  101. int k;
  102. cin >> k;
  103. vector<pll> vec, vec1;
  104. pll mn = mp(INF1, INF1);
  105. int ind = 0;
  106. for (int i = 0; i < k; ++i) {
  107. int a;
  108. cin >> a;
  109. vec.emplace_back(v[a - 1]);
  110. if (mn > v[a - 1]) {
  111. mn = v[a - 1];
  112. ind = i;
  113. }
  114. }
  115. reverse(all(vec));
  116. ind = k - ind - 1;
  117. for (int i = 0; i < k; ++i) {
  118. vec1.emplace_back(vec[(i + ind) % k]);
  119. }
  120. int ans = 0;
  121. for (auto &i : v1) if (in(i, vec1)) ++ans;
  122. cout << ans << "\n";
  123. }
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement