Advertisement
Guest User

Untitled

a guest
Dec 3rd, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define lli long long int
  4. #define fi first
  5. #define se second
  6. #define sc scanf
  7. #define pr printf
  8. #define pb push_back
  9. #define mp make_pair
  10. #define fin freopen( "input.txt", "r", stdin );
  11. #define fout freopen( "output.txt", "w", stdout );
  12.  
  13. const int N = 200200;
  14.  
  15. using namespace std;
  16.  
  17. struct point
  18. {
  19. long double x;
  20. long double y;
  21. };
  22.  
  23. int n;
  24. int m;
  25. bool used[N];
  26. point a[N];
  27. point b[N];
  28.  
  29. int orientation(point p, point q, point r)
  30. {
  31. long double val = (q.y - p.y) * (r.x - q.x) -
  32. (q.x - p.x) * (r.y - q.y);
  33. if (val == 0)
  34. return 0;
  35. return (val > 0)? 1: 2;
  36. }
  37.  
  38. bool cmp(point a, point b)
  39. {
  40. return a.x < b.x;
  41. }
  42.  
  43. long double dist(point a, point b)
  44. {
  45. return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  46. }
  47.  
  48. int get_pos_a(long double x)
  49. {
  50. int l = 1,
  51. r = m;
  52. while(l < r){
  53. int mid = (l + r) / 2;
  54. if(x >= b[mid + 1].x)
  55. l = mid + 1;
  56. else
  57. r = mid;
  58. }
  59. return l;
  60. }
  61.  
  62. int get_pos_b(long double x)
  63. {
  64. int l = 1,
  65. r = n;
  66. while(l < r){
  67. int mid = (l + r) / 2;
  68. if(x >= a[mid + 1].x)
  69. l = mid + 1;
  70. else
  71. r = mid;
  72. }
  73. return l;
  74. }
  75.  
  76. int main()
  77. {
  78. //fin("input.txt");
  79. //fout("output.txt");
  80. ios_base::sync_with_stdio(0);
  81. cin >> n >> m;
  82. for(int i = 1; i <= n; i++)
  83. cin >> a[i].x >> a[i].y;
  84. for(int i = 1; i <= m; i++)
  85. cin >> b[i].x >> b[i].y;
  86. long double mn = 1e9;
  87. vector < point > va, vb;
  88. for(int i = 1; i <= n; i++){
  89. int l = get_pos_a(a[i].x);
  90. if(a[i].x == b[l].x)
  91. continue;
  92. long double le = 2,
  93. re = 1e9;
  94. for(int j = 0; j < 200; j++){
  95. long double me = (le + re) / 2.0;
  96. point p = {a[i].x, a[i].y - me};
  97. if(orientation(b[l], b[l + 1], p) == 1)
  98. re = me;
  99. else
  100. le = me;
  101. }
  102. vb.pb({a[i].x, a[i].y - (le + re) / 2.0});
  103. }
  104. for(int i = 1; i <= m; i++){
  105. int l = get_pos_b(b[i].x);
  106. if(a[l].x == b[i].x)
  107. continue;
  108. long double le = 2,
  109. re = 1e9;
  110. for(int j = 0; j < 200; j++){
  111. long double me = (le + re) / 2.0;
  112. point p = {b[i].x, b[i].y + me};
  113. if(orientation(a[l], a[l + 1], p) == 2)
  114. re = me;
  115. else
  116. le = me;
  117. }
  118. va.pb({b[i].x, b[i].y + (le + re) / 2.0});
  119. }
  120. for(auto p: va)
  121. a[++n] = p;
  122. for(auto p: vb)
  123. b[++m] = p;
  124. sort(a + 1, a + n + 1, cmp);
  125. sort(b + 1, b + m + 1, cmp);
  126. for(int i = 1; i <= n; i++)
  127. mn = min(mn, dist(a[i], b[i]));
  128. int cnt = 0;
  129. used[n + 1] = used[0] = true;
  130. for(int i = n; i >= 1; i--){
  131. if(dist(a[i], b[i]) - mn < 1e-4)
  132. used[i] = true;
  133. }
  134. for(int i = 1; i <= n; i++)
  135. if(used[i + 1] == false && used[i] == true && used[i - 1] == false)
  136. cnt++;
  137. for(int i = 2; i <= n; i++){
  138. if(used[i] == false){
  139. cout << cnt + 1 << endl;
  140. return 0;
  141. }
  142. }
  143. cout << 0 << endl;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement