fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. const int MN = 1e5 + 10;
  7. typedef long long lld;
  8. struct Point
  9. {
  10. 	int x, y, id;
  11. 	Point(int _x = 0, int _y = 0, int _id = 0) : x(_x), y(_y), id(_id) {}
  12. };
  13.  
  14. int n, p, q;
  15.  
  16. //a-b, a-c
  17. int ccw(int ax, int ay, int bx, int by, int cx, int cy)
  18. {
  19. 	int dx1 = bx - ax;
  20. 	lld k = 1LL * (bx - ax) * (cy - ay) - 1LL * (by - ay) * (cx - ax);
  21. 	if(k > 0) return 1;
  22. 	if(k) return -1;
  23. 	return 0;
  24. }
  25.  
  26. int st[MN * 4];
  27. void build(int id = 1, int l = 0, int r = n - 1)
  28. {
  29. 	if(l == r){
  30. 		st[id] = 0;
  31. 		return;
  32. 	}
  33. 	int m = (l + r) >> 1;
  34. 	build(id << 1, l, m);
  35. 	build(id << 1 | 1, m + 1, r);
  36. 	st[id] = 0;
  37. }
  38.  
  39. void inc(int pos, int id = 1, int l = 0, int r = n - 1)
  40. {
  41. 	if(l == r){
  42. 		st[id]++;
  43. 		return;
  44. 	}
  45. 	int m = (l + r) >> 1;
  46. 	if(pos <= m){
  47. 		inc(pos, id << 1, l, m);
  48. 	}else{
  49. 		inc(pos, id << 1 | 1, m + 1, r);
  50. 	}
  51. 	st[id] = st[id << 1] + st[id << 1 | 1];
  52. }
  53.  
  54. int sum(int x, int y, int id = 1, int l = 0, int r = n - 1)
  55. {
  56. 	if(y < l || r < x) return 0;
  57. 	if(x <= l && r <= y) return st[id];
  58. 	int m = (l + r) >> 1;
  59. 	return sum(x, y, id << 1, l, m) + sum(x, y, id << 1 | 1, m + 1, r);
  60. }
  61.  
  62. int main()
  63. {
  64. 	ios_base::sync_with_stdio(false);
  65. 	cin.tie(0);
  66. 	int t;
  67. 	cin >> t;
  68. 	while(t--){
  69. 		cin >> n >> p >> q;
  70. 		vector<Point> points(n);
  71. 		for(int i = 0; i < n; ++i){
  72. 			cin >> points[i].x >> points[i].y;
  73. 		}
  74. 		sort(points.begin(), points.end(), [](const Point& a, const Point& b) -> bool{
  75. 			int k = ccw(p, 0, a.x, a.y, b.x, b.y);
  76. 			return k < 0;
  77. 		});
  78.  
  79. 		for(int i = 0; i < n; ++i){
  80. 			points[i].id = i;
  81. 		}
  82.  
  83. 		sort(points.begin(), points.end(), [](const Point& a, const Point& b) -> bool{
  84. 			int k = ccw(q, 0, a.x, a.y, b.x, b.y);
  85. 			return k < 0;
  86. 		});
  87.  
  88. 		build();
  89. 		lld ans = 0;
  90. 		for(int i = 0; i < n; ++i){
  91. 			ans += sum(points[i].id, n - 1);
  92. 			inc(points[i].id);
  93. 		}
  94. 		cout << ans << '\n';
  95. 	}
  96. }
Success #stdin #stdout 0s 5020KB
comments (?)
stdin
copy 
1
3 -5 5
-2 4
2 5
1 1
stdout
copy 
2
https://ideone.com/mRtIr4
algospot ANNIETIBBER
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!