Advertisement
Guest User

Untitled

a guest
May 26th, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.17 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("no-stack-protector")
  3. #pragma GCC optimize("unroll-loops")
  4. #pragma GCC optimize("unswitch-loops")
  5. #pragma GCC optimize("fast-math")
  6. #pragma GCC optimize("profile-reorder-functions")
  7. #pragma GCC optimize("profile-values")
  8. #pragma GCC optimize("tracer")
  9. #pragma GCC optimize("vpt")
  10. #pragma GCC optimize("rename-registers")
  11. #pragma GCC optimize("move-loop-invariants")
  12. #pragma GCC optimize("function-sections")
  13. #pragma GCC optimize("data-sections")
  14. #pragma GCC optimize("branch-target-load-optimize")
  15. #pragma GCC optimize("branch-target-load-optimize2")
  16. #pragma GCC optimize("btr-bb-exclusive")
  17. #pragma GCC target("sse2")
  18. #pragma GCC target("sse3")
  19. #pragma GCC target("sse4.1")
  20. #pragma GCC target("sse4.2")
  21. #pragma GCC target("popcnt")
  22. #pragma GCC target("abm")
  23. #pragma GCC target("mmx")
  24. #pragma GCC target("tune=native")
  25.  
  26. #include <iostream>
  27. #include <algorithm>
  28. #include <vector>
  29. #include <set>
  30.  
  31. using namespace std;
  32. using ll = long long;
  33.  
  34. struct Point {
  35. ll x, y;
  36. Point() {
  37. x = y = 0;
  38. }
  39. };
  40.  
  41. ll cur_ball;
  42.  
  43. struct segm {
  44. Point p, q;
  45. int id;
  46. segm() {
  47. id = -1;
  48. }
  49. bool operator<(const segm &s) const {
  50. ll dx = (q.x - p.x), sdx = (s.q.x - s.p.x), dy = (q.y - p.y), sdy = (s.q.y - s.p.y);
  51. return (p.y * dx + dy * (cur_ball - p.x)) * sdx > (s.p.y * sdx + sdy * (cur_ball - s.p.x)) * dx;
  52. }
  53. };
  54.  
  55. set<segm> s;
  56. vector<int> gr;
  57. vector<bool> used;
  58. vector<segm> segms;
  59. vector<ll> b;
  60. vector<ll> f;
  61. vector< pair<ll, pair<int, int>> > e;
  62.  
  63. int DFS(int v) {
  64. if (gr[v] == -1) {
  65. return v;
  66. } else {
  67. gr[v] = DFS(gr[v]);
  68. return gr[v];
  69. }
  70. }
  71.  
  72.  
  73. int main() {
  74. int n, m;
  75. cin >> n;
  76. segms.resize(n);
  77. used.resize(n);
  78. gr.resize(n);
  79. for (int i = 0; i < n; ++i) {
  80. segms[i].id = i;
  81. cin >> segms[i].p.x >> segms[i].p.y >> segms[i].q.x >> segms[i].q.y;
  82. if (segms[i].p.y < segms[i].q.y) {
  83. e.push_back({segms[i].p.x, {1, i}});
  84. e.push_back({segms[i].q.x, {4, i}});
  85. } else {
  86. e.push_back({segms[i].p.x, {0, i}});
  87. e.push_back({segms[i].q.x, {3, i}});
  88. }
  89. }
  90. cin >> m;
  91. f.resize(m);
  92. b.resize(m);
  93. for (int i = 0; i < m; ++i) {
  94. cin >> b[i];
  95. e.push_back({b[i], {2, i}});
  96. }
  97. sort(e.begin(), e.end());
  98. for (int i = 0; i < e.size(); ++i) {
  99. cur_ball = e[i].first;
  100. int t = e[i].second.first, j = e[i].second.second;
  101. if (t == 2)
  102. f[j] = (s.empty() ? -1 : s.begin()->id);
  103. if (t == 1 || t == 3) {
  104. set<segm>::iterator it = s.upper_bound(segms[j]);
  105. gr[j] = (it == s.end() ? -1 : it->id);
  106. }
  107. if (t == 0 || t == 1) {
  108. s.insert(segms[j]);
  109. }
  110. if (t == 3 || t == 4) {
  111. s.erase(segms[j]);
  112. }
  113. }
  114. for (int i = 0; i < m; ++i) {
  115. if (f[i] == -1) {
  116. cout << b[i] << "\n";
  117. } else {
  118. int j = DFS(f[i]);
  119. cout << ((segms[j].p.y < segms[j].q.y) ? segms[j].p.x : segms[j].q.x) << "\n";
  120. }
  121. }
  122. return 0;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement