제출 #102106

#제출 시각아이디문제언어결과실행 시간메모리
102106forestryksDragon 2 (JOI17_dragon2)C++14
0 / 100
4013 ms8320 KiB
/////////////////////////////////////////////////////////////////////////////////////////////// #include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout) #define f first #define s second #define x1 x1qwer #define y1 y1qwer #define right right123 #define left left123 #define foreach(it, v) for (auto it : v) #define rep(it, n) for (int it = 0; it < n; ++it) #define forin(it, l, r) for (int it = l; it < r; ++it) #define all(x) x.begin(), x.end() typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const double DINF = numeric_limits<double>::infinity(); const ll MOD = 1e9 + 7; const double EPS = 1e-7; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } mt19937 mmtw_(MOD); uniform_int_distribution<ll> rd_; ll randomll() { return rd_(mmtw_);} ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; } //////////////////////////////////////////////////////////////////////////////////////////////// struct pt { double x, y; }; double dot(const pt &a, const pt &b) { return a.x * b.x + a.y * b.y; } double cross(const pt &a, const pt &b) { return a.x * b.y - a.y * b.x; } pt operator-(const pt &a, const pt &b) { return {a.x - b.x, a.y - b.y}; } double ang(const pt &a, const pt &b) { return atan2(cross(a, b), dot(a, b)); } const int MAXN = 1e5 + 5; int n, m; pt a[MAXN]; int c[MAXN]; vector<int> ids[MAXN]; vector<pair<int, int>> q[MAXN]; pt A, B; double Ap[MAXN], Bp[MAXN], pA[MAXN], pB[MAXN]; int ans[MAXN]; int cnt[MAXN]; bool on_left[MAXN]; void solve() { rep(i, n) { pt p = a[i]; if (cross(p - A, B - A) < 0) { on_left[i] = true; Bp[i] = ang(B - A, p - A); Ap[i] = ang(B - A, p - B); pA[i] = ang(B - A, A - p); pB[i] = ang(B - A, B - p); } else { Ap[i] = ang(B - A, p - A); Bp[i] = ang(B - A, p - B); pB[i] = ang(B - A, A - p); pA[i] = ang(B - A, B - p); } // Ap[i] = ang(p - A, B - A); // Bp[i] = ang(p - B, B - A); // pA[i] = ang(A - p, B - A); // pB[i] = ang(B - p, B - A); // // Ap[i] = ang(B - A, p - A); // Bp[i] = ang(B - A, p - B); // pA[i] = ang(B - A, A - p); // pB[i] = ang(B - A, B - p); // if (Ap[i] > Bp[i]) swap(Ap[i], Bp[i]); // if (pA[i] > pB[i]) swap(pA[i], pB[i]); // if (cross(p - A, B - A) < 0) on_left[i] = true; } // rep(i, n) { // cout << Ap[i] << ' ' << Bp[i] << ' ' << pA[i] << ' ' << pB[i] << endl; // } for (int gr = 0; gr < m; ++gr) { memset(cnt, 0, sizeof(int) * m); for (auto i : ids[gr]) { for (int j = 0; j < n; ++j) { // if (i != 2 || j != 1) continue; // cout << on_left[i] << ' ' << Ap[i] << ' ' << Bp[i] << ' ' << pA[i] << ' ' << pB[i] << endl; // cout << on_left[j] << ' ' << Ap[j] << ' ' << Bp[j] << ' ' << pA[j] << ' ' << pB[j] << endl; if (on_left[i] == on_left[j]) { cnt[c[j]] += (pA[j] <= pA[i] && pB[i] <= pB[j]); } else { cnt[c[j]] += (pA[i] <= Ap[j] && Bp[j] <= pB[i]); } // cnt[c[j]] += (pA[i] < Ap[j] && Bp[j] < pB[i]); } } for (auto &it : q[gr]) { ans[it.s] = cnt[it.f]; } } // rep(i, n) { // cout << a[i].x << ' ' << a[i].y << " : " << Ap[i] << endl; // } } int main() { FAST_IO; cout.precision(10); cout.setf(ios::fixed); // while (true) { // pt a, b; // cin >> a.x >> a.y; // b = {1, 0}; // cout << ang(b, a) << endl; // } // return 0; cin >> n >> m; rep(i, n) { cin >> a[i].x >> a[i].y >> c[i]; c[i]--; ids[c[i]].push_back(i); } cin >> A.x >> A.y >> B.x >> B.y; int qc; cin >> qc; rep(i, qc) { int f, s; cin >> f >> s; f--; s--; q[f].push_back({s, i}); } solve(); rep(i, qc) { cout << ans[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...