| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 879384 | MilosMilutinovic | Dragon 2 (JOI17_dragon2) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct pt {
int x, y;
};
bool const operator == (pt a, pt b) {
return a.x == b.x && a.y == b.y;
}
struct angle {
pt a, b, c;
};
bool const operator < (angle p, angle q) {
int ps = orient(p.a, p.b, p.c);
int qs = orient(q.a, q.b, q.c);
if (ps == qs) {
return orient(p.a, q.a, p.b) == ps;
} else {
}
}
int orient(pt a, pt b, pt c) {
long long val = (b.y - a.y) * 1LL * (c.x - b.x) - (b.x - a.x) * 1LL * (c.y - b.y);
return (val == 0 ? 0 : (val > 0 ? 1 : -1)); // 1 clock, -1 counterclock
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<pt> p(n);
vector<int> c(n);
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y >> c[i];
--c[i];
}
pt a, b;
cin >> a.x >> a.y >> b.x >> b.y;
vector<vector<vector<int>>> ids(m, vector<vector<int>>(2));
vector<int> cnt(m);
for (int i = 0; i < n; i++) {
int o = orient(a, b, p[i]);
assert(o != 0);
int sd = (o == 1 ? 0 : 1);
ids[c[i]][sd].push_back(i);
cnt[c[i]] += 1;
}
vector<angle> all_a;
vector<angle> all_b;
for (int i = 0; i < m; i++) {
all_a.push_back({p[i], a, b});
all_b.push_back({p[i], b, a});
}
sort(all_a.begin(), all_a.end());
sort(all_b.begin(), all_b.end());
reverse(all_b.begin(), all_b.end());
vector<int> ia(n);
vector<int> ib(n);
for (int i = 0; i < n; i++) {
ia[i] = (int) (lower_bound(all_a.begin(), all_a.end(), {p[i], a, b}) - all_a.begin());
ib[i] = (int) (lower_bound(all_b.begin(), all_b.end(), {p[i], b, a}) - all_b.begin());
}
int q;
cin >> q;
vector<int> f(q), g(q);
vector<vector<vector<vector<array<int, 3>>>> pref_qs(2, vector<vector<array<int, 3>>>(m));
vector<vector<vector<vector<array<int, 3>>>> suff_qs(2, vector<vector<array<int, 3>>>(m));
for (int i = 0; i < m; i++) {
pref_qs[0][i].resize(cnt[i]);
pref_qs[1][i].resize(cnt[i]);
suff_qs[0][i].resize(cnt[i]);
suff_qs[1][i].resize(cnt[i]);
}
for (int i = 0; i < q; i++) {
cin >> f[i] >> g[i];
--f[i]; --g[i];
if (cnt[f[i]] < cnt[g[i]]) {
for (int sd = 0; sd < 2; sd++) {
}
}
}
return 0;
}