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;
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |