#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 |
1 |
Correct |
18 ms |
1116 KB |
Output is correct |
2 |
Correct |
29 ms |
1116 KB |
Output is correct |
3 |
Correct |
36 ms |
1116 KB |
Output is correct |
4 |
Correct |
27 ms |
1368 KB |
Output is correct |
5 |
Correct |
20 ms |
1368 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
1116 KB |
Output is correct |
8 |
Correct |
8 ms |
1116 KB |
Output is correct |
9 |
Correct |
8 ms |
1116 KB |
Output is correct |
10 |
Correct |
8 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1700 ms |
2456 KB |
Output is correct |
2 |
Correct |
3251 ms |
2532 KB |
Output is correct |
3 |
Correct |
70 ms |
2784 KB |
Output is correct |
4 |
Correct |
9 ms |
2648 KB |
Output is correct |
5 |
Correct |
9 ms |
2652 KB |
Output is correct |
6 |
Correct |
1190 ms |
2548 KB |
Output is correct |
7 |
Correct |
1186 ms |
2764 KB |
Output is correct |
8 |
Correct |
743 ms |
2544 KB |
Output is correct |
9 |
Correct |
645 ms |
2396 KB |
Output is correct |
10 |
Correct |
722 ms |
2588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
1116 KB |
Output is correct |
2 |
Correct |
29 ms |
1116 KB |
Output is correct |
3 |
Correct |
36 ms |
1116 KB |
Output is correct |
4 |
Correct |
27 ms |
1368 KB |
Output is correct |
5 |
Correct |
20 ms |
1368 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
2 ms |
1116 KB |
Output is correct |
8 |
Correct |
8 ms |
1116 KB |
Output is correct |
9 |
Correct |
8 ms |
1116 KB |
Output is correct |
10 |
Correct |
8 ms |
1116 KB |
Output is correct |
11 |
Correct |
1700 ms |
2456 KB |
Output is correct |
12 |
Correct |
3251 ms |
2532 KB |
Output is correct |
13 |
Correct |
70 ms |
2784 KB |
Output is correct |
14 |
Correct |
9 ms |
2648 KB |
Output is correct |
15 |
Correct |
9 ms |
2652 KB |
Output is correct |
16 |
Correct |
1190 ms |
2548 KB |
Output is correct |
17 |
Correct |
1186 ms |
2764 KB |
Output is correct |
18 |
Correct |
743 ms |
2544 KB |
Output is correct |
19 |
Correct |
645 ms |
2396 KB |
Output is correct |
20 |
Correct |
722 ms |
2588 KB |
Output is correct |
21 |
Correct |
1675 ms |
2560 KB |
Output is correct |
22 |
Correct |
3250 ms |
2540 KB |
Output is correct |
23 |
Correct |
2965 ms |
2816 KB |
Output is correct |
24 |
Correct |
727 ms |
3028 KB |
Output is correct |
25 |
Correct |
40 ms |
2860 KB |
Output is correct |
26 |
Correct |
30 ms |
2648 KB |
Output is correct |
27 |
Correct |
11 ms |
2648 KB |
Output is correct |
28 |
Correct |
11 ms |
2652 KB |
Output is correct |
29 |
Correct |
3440 ms |
2664 KB |
Output is correct |
30 |
Correct |
73 ms |
4304 KB |
Output is correct |
31 |
Correct |
27 ms |
4320 KB |
Output is correct |
32 |
Correct |
57 ms |
4452 KB |
Output is correct |
33 |
Correct |
811 ms |
4708 KB |
Output is correct |
34 |
Correct |
29 ms |
4644 KB |
Output is correct |
35 |
Correct |
28 ms |
4540 KB |
Output is correct |
36 |
Correct |
30 ms |
4536 KB |
Output is correct |
37 |
Correct |
30 ms |
4688 KB |
Output is correct |
38 |
Correct |
1394 ms |
4580 KB |
Output is correct |
39 |
Correct |
1117 ms |
4432 KB |
Output is correct |
40 |
Correct |
826 ms |
4432 KB |
Output is correct |
41 |
Correct |
2959 ms |
4588 KB |
Output is correct |
42 |
Correct |
2156 ms |
4348 KB |
Output is correct |
43 |
Correct |
1911 ms |
4392 KB |
Output is correct |
44 |
Correct |
2129 ms |
3548 KB |
Output is correct |
45 |
Correct |
1089 ms |
3368 KB |
Output is correct |
46 |
Correct |
646 ms |
3416 KB |
Output is correct |
47 |
Correct |
1364 ms |
3540 KB |
Output is correct |
48 |
Correct |
858 ms |
3596 KB |
Output is correct |
49 |
Correct |
593 ms |
3984 KB |
Output is correct |