Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("unswitch-loops")
- #pragma GCC optimize("fast-math")
- #pragma GCC optimize("profile-reorder-functions")
- #pragma GCC optimize("profile-values")
- #pragma GCC optimize("tracer")
- #pragma GCC optimize("vpt")
- #pragma GCC optimize("rename-registers")
- #pragma GCC optimize("move-loop-invariants")
- #pragma GCC optimize("function-sections")
- #pragma GCC optimize("data-sections")
- #pragma GCC optimize("branch-target-load-optimize")
- #pragma GCC optimize("branch-target-load-optimize2")
- #pragma GCC optimize("btr-bb-exclusive")
- #pragma GCC target("sse2")
- #pragma GCC target("sse3")
- #pragma GCC target("sse4.1")
- #pragma GCC target("sse4.2")
- #pragma GCC target("popcnt")
- #pragma GCC target("abm")
- #pragma GCC target("mmx")
- #pragma GCC target("tune=native")
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <set>
- using namespace std;
- using ll = long long;
- struct Point {
- ll x, y;
- Point() {
- x = y = 0;
- }
- };
- ll cur_ball;
- struct segm {
- Point p, q;
- int id;
- segm() {
- id = -1;
- }
- bool operator<(const segm &s) const {
- 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);
- return (p.y * dx + dy * (cur_ball - p.x)) * sdx > (s.p.y * sdx + sdy * (cur_ball - s.p.x)) * dx;
- }
- };
- set<segm> s;
- vector<int> gr;
- vector<bool> used;
- vector<segm> segms;
- vector<ll> b;
- vector<ll> f;
- vector< pair<ll, pair<int, int>> > e;
- int DFS(int v) {
- if (gr[v] == -1) {
- return v;
- } else {
- gr[v] = DFS(gr[v]);
- return gr[v];
- }
- }
- int main() {
- int n, m;
- cin >> n;
- segms.resize(n);
- used.resize(n);
- gr.resize(n);
- for (int i = 0; i < n; ++i) {
- segms[i].id = i;
- cin >> segms[i].p.x >> segms[i].p.y >> segms[i].q.x >> segms[i].q.y;
- if (segms[i].p.y < segms[i].q.y) {
- e.push_back({segms[i].p.x, {1, i}});
- e.push_back({segms[i].q.x, {4, i}});
- } else {
- e.push_back({segms[i].p.x, {0, i}});
- e.push_back({segms[i].q.x, {3, i}});
- }
- }
- cin >> m;
- f.resize(m);
- b.resize(m);
- for (int i = 0; i < m; ++i) {
- cin >> b[i];
- e.push_back({b[i], {2, i}});
- }
- sort(e.begin(), e.end());
- for (int i = 0; i < e.size(); ++i) {
- cur_ball = e[i].first;
- int t = e[i].second.first, j = e[i].second.second;
- if (t == 2)
- f[j] = (s.empty() ? -1 : s.begin()->id);
- if (t == 1 || t == 3) {
- set<segm>::iterator it = s.upper_bound(segms[j]);
- gr[j] = (it == s.end() ? -1 : it->id);
- }
- if (t == 0 || t == 1) {
- s.insert(segms[j]);
- }
- if (t == 3 || t == 4) {
- s.erase(segms[j]);
- }
- }
- for (int i = 0; i < m; ++i) {
- if (f[i] == -1) {
- cout << b[i] << "\n";
- } else {
- int j = DFS(f[i]);
- cout << ((segms[j].p.y < segms[j].q.y) ? segms[j].p.x : segms[j].q.x) << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement