fork download
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <unordered_map>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long int64;
  9.  
  10. struct Point {
  11. Point(int64 x, int64 y) : x(x), y(y) {}
  12. int64 x;
  13. int64 y;
  14. };
  15.  
  16. bool compareP(Point const& a, Point const& b)
  17. {
  18. if(a.x != b.x) return a.x < b.x;
  19. else a.y < b.y;
  20. }
  21.  
  22. bool operator<(Point const& a, Point const& b) {
  23. return a.x != b.x ? a.x < b.x : a.y < b.y;
  24. }
  25.  
  26. struct Cut {
  27. Cut(Point a, Point b) : a(a), b(b) {}
  28. Point a;
  29. Point b;
  30. };
  31. bool operator<(Cut const& lt, Cut const& rt) { return lt.a < rt.a; }
  32.  
  33. bool compareC(Cut const& lt, Cut const& rt)
  34. {
  35. return compareP(lt.a,rt.a);
  36. }
  37.  
  38.  
  39.  
  40. bool IsRight(Cut const& cut, Point const& point) {
  41. int64 dx1 = cut.a.x - point.x;
  42. int64 dy1 = cut.a.y - point.y;
  43. int64 dx2 = cut.b.x - point.x;
  44. int64 dy2 = cut.b.y - point.y;
  45. int64 t = dx1 * dy2 - dx2 * dy1;
  46. return t < 0;
  47. }
  48.  
  49. int64 BinarySearch(vector<Cut> const& cuts, Point const& point, int lo, int hi) {
  50. //int lo = 0, hi = cuts.size();
  51. if(lo == hi) return lo;
  52. int mid = (lo + hi)/2;
  53. if(IsRight(cuts[mid],point)) BinarySearch(cuts,point,lo,mid);
  54. else BinarySearch(cuts,point,mid+1,hi);
  55. //while (lo < hi) {
  56. //int mid = (lo + hi) / 2;
  57. //if (IsRight(cuts[mid], point)) hi = mid; else lo = mid + 1;
  58. //}
  59. // return lo;
  60. }
  61.  
  62. int main() {
  63. int X, Y;
  64. scanf("%d%d", &X, &Y);
  65. vector<Point> Q;
  66. int nQ;
  67. scanf("%d", &nQ);
  68. for (int i = 0; i < nQ; ++i) {
  69. int x, y;
  70. scanf("%d%d", &x, &y);
  71. Q.push_back(Point(x, y));
  72. }
  73.  
  74. vector<Cut> H;
  75. int nH;
  76. scanf("%d", &nH);
  77. for (int i = 0; i < nH; ++i) {
  78. int y1, y2;
  79. scanf("%d%d", &y1, &y2);
  80. H.push_back(Cut(Point(0, y1), Point(X, y2)));
  81. }
  82. sort(H.begin(), H.end());
  83.  
  84. vector<Cut> V;
  85. int nV;
  86. scanf("%d", &nV);
  87. for (int i = 0; i < nV; ++i) {
  88. int x1, x2;
  89. scanf("%d%d", &x1, &x2);
  90. V.push_back(Cut(Point(x1, Y), Point(x2, 0)));
  91. }
  92. sort(V.begin(), V.end());
  93.  
  94. int mx = 0;
  95. std::unordered_map<int64, int> cnt;
  96. for (int i = 0; i < nQ; ++i) {
  97. mx = max(mx, ++cnt[BinarySearch(H, Q[i],0,H.size()) << 32 | BinarySearch(V, Q[i],0,V.size())]);
  98. }
  99. printf("%d\n", mx);
  100. return 0;
  101. }
  102.  
Success #stdin #stdout 0s 3472KB
stdin
53 59
200
25 21
32 30
44 24
46 28
45 35
44 44
8 22
30 23
4 23
16 25
48 22
1 25
31 22
9 24
38 29
39 31
42 27
43 29
37 34
48 36
26 37
45 21
32 24
41 28
46 24
32 28
31 38
34 29
43 35
45 30
16 28
41 31
36 24
4 29
6 28
39 36
38 30
44 38
38 31
45 33
36 34
36 38
24 24
40 33
31 28
38 17
32 38
27 35
33 39
13 28
50 20
31 45
39 52
36 44
37 30
48 25
7 32
3 31
16 34
44 32
2 33
17 38
50 27
34 33
48 31
38 32
48 33
3 26
39 35
40 29
39 37
34 31
33 32
28 28
41 33
42 29
40 38
40 31
45 32
2 23
51 24
41 29
9 31
40 16
46 41
33 38
30 35
37 28
30 25
51 33
33 27
43 22
47 28
45 25
35 29
44 28
43 18
50 37
18 39
43 30
36 28
28 27
30 24
8 33
46 31
48 24
36 16
25 31
49 31
1 30
22 32
45 39
39 27
34 26
42 34
51 26
23 28
52 25
44 33
50 36
51 28
30 43
44 43
39 34
30 28
41 32
29 32
49 41
21 42
43 23
34 38
26 26
45 27
37 32
49 32
6 26
48 26
41 27
19 41
40 24
33 31
19 36
41 34
6 23
31 43
46 33
47 24
24 19
41 43
36 19
2 29
22 36
37 35
48 40
47 32
31 44
33 28
50 30
40 23
37 29
32 31
29 27
32 27
10 30
27 39
13 38
31 42
17 39
43 44
33 33
28 39
44 37
40 25
1 36
42 23
39 29
30 30
50 22
36 35
36 30
41 26
47 30
51 30
33 24
26 32
13 33
1 33
32 42
39 43
33 22
29 31
39 42
6 30
34 35
29 29
24 23
24 39
33 43
33 23
28 31
10
36 41
57 55
24 37
18 17
21 19
2 11
44 46
48 49
23 26
52 51
11
52 51
33 44
15 26
2 6
48 49
27 35
5 12
7 13
14 24
40 47
9 18
stdout
22