fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <map>
  8. #include <set>
  9. #include <string>
  10. #include <cstring>
  11. #include <queue>
  12. #include <cassert>
  13. #define rf freopen("in.in", "r", stdin)
  14. #define wf freopen("out.out", "w", stdout)
  15. #define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
  16. using namespace std;
  17. const int mx = 1e5 + 10, mod = 1e9+7;
  18. #define pi pair<int, int>
  19. #define ff first
  20. #define ss second
  21. #define mp make_pair
  22.  
  23. pi red_points[mx], black_points[mx];
  24. int blacks_inside[111][111];
  25. const int base = 1e4;
  26. int n, m, q;
  27.  
  28. int cross_prod(pi pti, pi ptj, pi ptk)
  29. {
  30. 	int ix = pti.ff, iy = pti.ss;
  31. 	int jx = ptj.ff, jy = ptj.ss;
  32. 	int kx = ptk.ff, ky = ptk.ss;
  33.  
  34. 	return (ix - jx) * (ky - jy) - (iy - jy) * (kx - jx);
  35. }
  36.  
  37. int test_inside(pi pti, pi ptj, pi ptk, pi pts)
  38. {
  39. 	int ix = pti.ff, iy = pti.ss;
  40. 	int jx = ptj.ff, jy = ptj.ss;
  41. 	int kx = ptk.ff, ky = ptk.ss;
  42. 	int sx = pts.ff, sy = pts.ss;
  43.  
  44.    	int as_x = sx-ix, as_y = sy-iy;
  45.     	bool s_ab = (jx-ix)*as_y-(jy-iy)*as_x > 0;
  46.  
  47.     	if((kx-ix)*as_y-(ky-iy)*as_x > 0 == s_ab)
  48. 		return 0;
  49.  
  50.     	if((kx-jx)*(sy-jy)-(ky-jy)*(sx-jx) > 0 != s_ab)
  51. 		return 0;
  52.  
  53. 	return 1;
  54. }
  55.  
  56. void count_blacks_inside(int i, int j)
  57. {
  58. 	pi pti = red_points[i], ptj = red_points[j];
  59.  
  60. 	if(cross_prod(pti, mp(0, 0), ptj) <= 0)
  61. 		return;
  62.  
  63. 	rep(p, 1, m)
  64. 		blacks_inside[i][j] += test_inside(pti, mp(0, 0), ptj, black_points[p]);
  65.  
  66. 	blacks_inside[j][i] = -blacks_inside[i][j];
  67. }
  68.  
  69. int main()
  70. {
  71. 	//rf;// wf;
  72. 	ios::sync_with_stdio(0);
  73.  
  74. 	cin >> n >> m;
  75. 	rep(i, 1, n)
  76. 	{
  77. 		int x, y;
  78. 		cin >> x >> y;
  79. 		x += base; y += base;
  80.  
  81. 		red_points[i] = mp(x, y);
  82. 	}
  83.  
  84. 	rep(i, 1, m)
  85. 	{
  86. 		int x, y;
  87. 		cin >> x >> y;
  88. 		x += base; y += base;
  89.  
  90. 		black_points[i] = mp(x, y);
  91. 	}
  92.  
  93. 	rep(i, 1, n) rep(j, 1, n)
  94. 		count_blacks_inside(i, j);
  95.  
  96. 	cin >> q;
  97. 	while(q--)
  98. 	{
  99. 		int k;
  100. 		cin >> k;
  101.  
  102. 		int prev, cur, start;
  103. 		cin >> prev; start = prev;
  104.  
  105. 		int ans = 0;
  106. 		for(int i = 1; i<k; ++i)
  107. 		{
  108.  
  109. 			cin >> cur;
  110. 			ans += blacks_inside[prev][cur];
  111.  
  112. 			prev = cur;
  113. 		}
  114. 		ans += blacks_inside[cur][start];
  115.  
  116. 		cout << abs(ans) << '\n';
  117. 	}
  118.  
  119. 	return 0;
  120. }
  121.  
Success #stdin #stdout 0s 5016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EJOhDb
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!