제출 #894672

#제출 시각아이디문제언어결과실행 시간메모리
894672OAleksaDragon 2 (JOI17_dragon2)C++14
60 / 100
4062 ms3976 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; }; point a[N]; point s, e; int n, m, d1, e1, d2, e2, q, c[N]; vector<point> g[N]; int cross(point a, point b, point c) { point v = {b.x - a.x, b.y - a.y}; point v1 = {c.x - a.x, c.y - a.y}; int r = v1.x * v.y - v1.y * v.x; assert(r != 0); if (r > 0) return 1; //desno return -1; //levo } 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...