fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <assert.h>
  4. #include <set>
  5. #include <map>
  6. #include <complex>
  7. #include <iostream>
  8. #include <time.h>
  9. #include <math.h>
  10. #include <stack>
  11. #include <stdlib.h>
  12. #include <memory.h>
  13. #include <bitset>
  14. #include <math.h>
  15. #include <string>
  16. #include <string.h>
  17. #include <queue>
  18. #include <vector>
  19.  
  20. using namespace std;
  21.  
  22. const int MaxN = 3e3 + 10;
  23. const int MaxC = 1e4 + 10;
  24. const int INF = 1e9;
  25. const int MOD = 1e9 + 7;
  26.  
  27. struct Point {
  28.   int x, y;
  29. };
  30.  
  31. int cw(const Point &a, const Point &b, const Point &c) {
  32.   return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
  33. }
  34.  
  35. bool inTriangle(const Point &a, const Point &b, const Point &c, const Point &d) {
  36.   int bcd = abs(cw(b, c, d));
  37.   int acd = abs(cw(a, c, d));
  38.   int abd = abs(cw(a, b, d));
  39.   int abc = abs(cw(a, b, c));
  40.   return abc == abd + acd + bcd;
  41. }
  42.  
  43. Point white[MaxN], black[MaxN], zero;
  44. int cnt[MaxN][MaxN], ord[MaxN], n, m, q, k;
  45.  
  46. int main() {
  47. //  freopen("input.txt", "r", stdin);
  48.   ios::sync_with_stdio(false);
  49.   cin.tie(NULL);
  50.   cin >> n >> m;
  51.   for (int i = 0; i < n; ++i) {
  52.     cin >> white[i].x >> white[i].y;
  53.     white[i].x += MaxC;
  54.     white[i].y += MaxC;
  55.   }
  56.   for (int i = 0; i < m; ++i) {
  57.     cin >> black[i].x >> black[i].y;
  58.     black[i].x += MaxC;
  59.     black[i].y += MaxC;
  60.   }
  61.   for (int i = 0; i < n; ++i) {
  62.     for (int j = 0; j < n; ++j) {
  63.       if (cw(white[i], zero, white[j]) > 0) {
  64.         for (int k = 0; k < m; ++k) {
  65.           if (inTriangle(white[i], zero, white[j], black[k]) == true) {
  66.             cnt[i][j]++;
  67.           }
  68.         }
  69.         cnt[j][i] = -cnt[i][j];
  70.       }
  71.     }
  72.   }
  73.   cin >> q;
  74.   for (int qi = 0; qi < q; ++qi) {
  75.     cin >> k;
  76.     for (int i = 0; i < k; ++i) {
  77.       cin >> ord[i];
  78.       ord[i]--;
  79.     }
  80.     int ans = 0;
  81.     for (int i = 0; i < k; ++i) {
  82.       int ni = i == k - 1 ? 0 : i + 1;
  83.       ans += cnt[ord[i]][ord[ni]];
  84.     }
  85.     cout << abs(ans) << '\n';
  86.   }
  87.   return 0;
  88. }
Success #stdin #stdout 0s 38904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/biHz9k
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!