#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<long double>
#define vvi vector<vector<int>>
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define pii pair<long double, long double>
#define vpii vector<pair<long double, long double>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define mii map<int,int>
#define mll map<long long int, long long int>
#define mivi map<int,vector<int>>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
using namespace std;
pii line(pii a, pii b){
if(b.first != a.first)return {(b.second - a.second) / (b.first - a.first), a.second - a.first * ((b.second - a.second) / (b.first - a.first))};
else return {(b.second - a.second) / (b.first - a.first), a.first};
}
pii intersect(pii a, pii b){
if(isinf(a.first)){
return {a.second, b.first * a.second + b.second};
}
int x = (b.second - a.second)/(a.first - b.first);
return {x, a.first * x + a.second};
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin(".in");
//ofstream cout(".out");
int n,m;
cin>>n>>m;
//cout<<line({1,-1}, {1,1}).first<<' '<<line({1,-1}, {1,1}).second<<'\n';
vpii tribe[m+1];
f0r(i, n){
long double a,b;
int c;
cin>>a>>b>>c;
tribe[c].pb({a,b});
}
long double x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
pii mainline = line({x1,y1}, {x2,y2});
int ub = max(y1, y2);
int lb = min(y1, y2);
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
int ans = 0;
f0r(i, tribe[a].size()){
f0r(j, tribe[b].size()){
pii attacker = tribe[a][i];
pii victim = tribe[b][j];
pii l = line(attacker, victim);
//cout<<l.first<<' '<<l.second<<' '<<mainline.first<<' '<<mainline.second<<'\n';
pii kousaten = intersect(l, mainline);
//cout<<kousaten.first<<' '<<kousaten.second<<'\n';
bool ok = 1;
if(l.first == mainline.first && l.second != mainline.second)ok = 0;
if(attacker.second > victim.second && kousaten.second > attacker.second){
ok = 0;
}
if(attacker.second < victim.second && kousaten.second < attacker.second){
ok = 0;
}
if(attacker.second == victim.second && (kousaten.first > max(attacker.first, victim.first)|| kousaten.first < min(attacker.first, victim.first)))ok = 0;
if(kousaten.second > ub || kousaten.second < lb)ok = 0;
if(ok)ans++;
}
}
cout<<ans<<'\n';
}
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:16:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define f0r(i,n) for(int i=0;i<n;i++)
......
58 | f0r(i, tribe[a].size()){
| ~~~~~~~~~~~~~~~~~~
dragon2.cpp:58:3: note: in expansion of macro 'f0r'
58 | f0r(i, tribe[a].size()){
| ^~~
dragon2.cpp:16:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define f0r(i,n) for(int i=0;i<n;i++)
......
59 | f0r(j, tribe[b].size()){
| ~~~~~~~~~~~~~~~~~~
dragon2.cpp:59:4: note: in expansion of macro 'f0r'
59 | f0r(j, tribe[b].size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
604 KB |
Output is correct |
| 2 |
Correct |
150 ms |
600 KB |
Output is correct |
| 3 |
Correct |
154 ms |
752 KB |
Output is correct |
| 4 |
Correct |
53 ms |
1360 KB |
Output is correct |
| 5 |
Correct |
22 ms |
1456 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4033 ms |
1988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
604 KB |
Output is correct |
| 2 |
Correct |
150 ms |
600 KB |
Output is correct |
| 3 |
Correct |
154 ms |
752 KB |
Output is correct |
| 4 |
Correct |
53 ms |
1360 KB |
Output is correct |
| 5 |
Correct |
22 ms |
1456 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
