제출 #894676

#제출 시각아이디문제언어결과실행 시간메모리
894676OAleksaDragon 2 (JOI17_dragon2)C++14
100 / 100
3440 ms4708 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define f first #define s second const int N = 3e4 + 69; struct point { int x, y; } a[N], s, e; vector<point> g[N]; int n, m, q, c[N]; int cross(point a, point b, point c) { return (c.x - a.x) * (b.y - a.y) > (c.y - a.y) * (b.x - a.x); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while (tt--) { cin >> n >> m; for (int i = 1;i <= n;i++) { cin >> a[i].x >> a[i].y >> c[i]; g[c[i]].push_back(a[i]); } cin >> s.x >> s.y >> e.x >> e.y; cin >> q; while (q--) { int a, b; cin >> a >> b; int ans = 0; for (auto u : g[a]) { int d5 = cross(s, e, u); for (auto t : g[b]) { //ili je u trouglu //ili se seku duzi int d = cross(u, s, t); int d1 = cross(s, e, t); int d2 = cross(e, u ,t); int d3 = cross(u, t, s); int d4 = cross(u, t, e); if (d == d1 && d1 == d2) ++ans; else if (d3 != d4 && d5 != d1) ++ans; } } cout << ans << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...