#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
int X[30005];
int Y[30005];
int C[50005];
int X1, Y1, X2, Y2;
vector<vector<int>> Color;
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
int i, j;
for(i=0;i<N;i++) cin >> X[i] >> Y[i] >> C[i];
cin >> X1 >> Y1 >> X2 >> Y2;
X2 -= X1;
Y2 -= Y1;
for(i=0;i<N;i++) {
X[i] -= X1;
Y[i] -= Y1;
C[i]--;
}
X1 = Y1 = 0;
if(X2<0) {
X2 *= -1;
for(i=0;i<N;i++) X[i] *= -1;
}
if(Y2<0) {
Y2 *= -1;
for(i=0;i<N;i++) Y[i] *= -1;
}
for(i=0;i<N;i++) {
int x = Y2*X[i] - X2*Y[i];
int y = X2*X[i] + Y2*Y[i];
X[i] = x;
Y[i] = y;
}
Y2 = X2*X2+Y2*Y2;
X2 = 0;
Color.resize(M);
for(i=0;i<N;i++) Color[C[i]].push_back(i);
int Q;
cin >> Q;
while(Q--) {
int F, G;
cin >> F >> G;
F--;
G--;
int ans = 0;
for(i=0;i<Color[F].size();i++) {
for(j=0;j<Color[G].size();j++) {
int l = Color[F][i];
int r = Color[G][j];
if(X[l]>0&&X[r]>0&&X[l]<=X[r]) continue;
if(X[l]<0&&X[r]<0&&X[r]<=X[l]) continue;
if(X[l]>X[r]) swap(l, r);
__int128 c = -1 * (__int128)X[l]*Y[r] + (__int128)X[r] * Y[l];
__int128 c2 = (__int128)(X[r]-X[l]) * Y2;
if(c >= 0&& c <= c2) ans++;
}
}
cout << ans << '\n';
}
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:53:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(i=0;i<Color[F].size();i++) {
| ~^~~~~~~~~~~~~~~~
dragon2.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(j=0;j<Color[G].size();j++) {
| ~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
340 KB |
Output is correct |
2 |
Correct |
34 ms |
468 KB |
Output is correct |
3 |
Correct |
49 ms |
460 KB |
Output is correct |
4 |
Correct |
35 ms |
636 KB |
Output is correct |
5 |
Correct |
28 ms |
708 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
11 ms |
460 KB |
Output is correct |
9 |
Correct |
9 ms |
452 KB |
Output is correct |
10 |
Correct |
11 ms |
456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1869 ms |
1424 KB |
Output is correct |
2 |
Correct |
3495 ms |
1368 KB |
Output is correct |
3 |
Correct |
82 ms |
2204 KB |
Output is correct |
4 |
Correct |
11 ms |
2088 KB |
Output is correct |
5 |
Correct |
13 ms |
3156 KB |
Output is correct |
6 |
Correct |
1597 ms |
2016 KB |
Output is correct |
7 |
Correct |
1618 ms |
2012 KB |
Output is correct |
8 |
Correct |
975 ms |
2040 KB |
Output is correct |
9 |
Correct |
779 ms |
1888 KB |
Output is correct |
10 |
Correct |
992 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
340 KB |
Output is correct |
2 |
Correct |
34 ms |
468 KB |
Output is correct |
3 |
Correct |
49 ms |
460 KB |
Output is correct |
4 |
Correct |
35 ms |
636 KB |
Output is correct |
5 |
Correct |
28 ms |
708 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
11 ms |
460 KB |
Output is correct |
9 |
Correct |
9 ms |
452 KB |
Output is correct |
10 |
Correct |
11 ms |
456 KB |
Output is correct |
11 |
Correct |
1869 ms |
1424 KB |
Output is correct |
12 |
Correct |
3495 ms |
1368 KB |
Output is correct |
13 |
Correct |
82 ms |
2204 KB |
Output is correct |
14 |
Correct |
11 ms |
2088 KB |
Output is correct |
15 |
Correct |
13 ms |
3156 KB |
Output is correct |
16 |
Correct |
1597 ms |
2016 KB |
Output is correct |
17 |
Correct |
1618 ms |
2012 KB |
Output is correct |
18 |
Correct |
975 ms |
2040 KB |
Output is correct |
19 |
Correct |
779 ms |
1888 KB |
Output is correct |
20 |
Correct |
992 ms |
1884 KB |
Output is correct |
21 |
Correct |
1746 ms |
2032 KB |
Output is correct |
22 |
Correct |
3460 ms |
2100 KB |
Output is correct |
23 |
Correct |
3501 ms |
2264 KB |
Output is correct |
24 |
Correct |
805 ms |
3432 KB |
Output is correct |
25 |
Correct |
50 ms |
3628 KB |
Output is correct |
26 |
Correct |
40 ms |
4424 KB |
Output is correct |
27 |
Correct |
15 ms |
3648 KB |
Output is correct |
28 |
Correct |
14 ms |
3540 KB |
Output is correct |
29 |
Correct |
3793 ms |
4360 KB |
Output is correct |
30 |
Correct |
74 ms |
4028 KB |
Output is correct |
31 |
Correct |
45 ms |
4164 KB |
Output is correct |
32 |
Correct |
70 ms |
4172 KB |
Output is correct |
33 |
Correct |
901 ms |
4212 KB |
Output is correct |
34 |
Correct |
40 ms |
4352 KB |
Output is correct |
35 |
Correct |
35 ms |
4172 KB |
Output is correct |
36 |
Correct |
37 ms |
4204 KB |
Output is correct |
37 |
Correct |
37 ms |
4348 KB |
Output is correct |
38 |
Correct |
1482 ms |
4496 KB |
Output is correct |
39 |
Correct |
1238 ms |
4360 KB |
Output is correct |
40 |
Correct |
899 ms |
4232 KB |
Output is correct |
41 |
Correct |
3131 ms |
4352 KB |
Output is correct |
42 |
Correct |
2615 ms |
4108 KB |
Output is correct |
43 |
Correct |
2253 ms |
4096 KB |
Output is correct |
44 |
Correct |
2134 ms |
2704 KB |
Output is correct |
45 |
Correct |
1105 ms |
2780 KB |
Output is correct |
46 |
Correct |
684 ms |
2832 KB |
Output is correct |
47 |
Correct |
1886 ms |
2804 KB |
Output is correct |
48 |
Correct |
977 ms |
2712 KB |
Output is correct |
49 |
Correct |
646 ms |
2864 KB |
Output is correct |