#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int K = 100;
struct slope {
int x, y;
slope(int _x, int _y): x(_x), y(_y) {}
slope operator - () {return slope(-x,-y);}
};
struct fenwick {
int n;
vector<int> fw;
fenwick(int _n): n(_n+1), fw(_n+1,0) {}
void up(int x, int u) {
for(x++;x<n;x+=(x&(-x)))
fw[x] += u;
}
int qry(int x) {
int ans = 0;
for(x++;x;x-=(x&(-x)))
ans += fw[x];
return ans;
}
};
/*
Seriously?
O(cbrt(N^4 * Q * log^2 N))???
*/
int main() {
int n, m;
cin >> n >> m;
vector<pair<int,int>> dragon[m];
for(int i=0;i<n;i++) {
int a, b, c;
cin >> a >> b >> c;
dragon[c-1].push_back({a,b});
}
int d1, e1, d2, e2;
cin >> d1 >> e1 >> d2 >> e2;
auto cmp0 = [](slope a, slope b) {
return (1LL * a.y * b.x < 1LL * a.x * b.y);
};
auto cmp1 = [&cmp0,d1,e1,d2,e2](slope x, slope y) {
slope z(d2 - d1, e2 - e1);
if(cmp0(x,z) == cmp0(y,z))
return cmp0(x,y);
return cmp0(x,z);
};
auto cmp2 = [&cmp0,d1,e1,d2,e2](slope x, slope y) {
slope z(d1 - d2, e1 - e2);
if(cmp0(x,z) == cmp0(y,z))
return cmp0(x,y);
return cmp0(x,z);
};
vector<int> spec;
for(int i=0;i<m;i++)
if(dragon[i].size() > K)
spec.push_back(i);
int s = spec.size();
int ans1[s][m], ans2[m][s];
for(int i=0;i<s;i++) {
vector<tuple<slope,slope,int>> help;
vector<slope> disc;
int g = spec[i];
for(auto [x, y]: dragon[g]) {
help.push_back({slope(x-d1,y-e1), slope(x-d2,y-e2), 0});
disc.push_back(slope(x-d2,y-e2));
}
for(int f=0;f<n;f++)
if(f != g)
for(auto [x, y]: dragon[f]) {
slope fi = slope(x-d1,y-e1);
if(cmp1(-fi,fi))
fi = -fi;
slope se = slope(x-d2,y-e2);
if(cmp2(-se,se))
se = -se;
help.push_back({fi, se, f+1});
help.push_back({fi, -se, -f-1});
help.push_back({-fi, se, f+1});
help.push_back({-fi, -se, -f-1});
disc.push_back(se);
disc.push_back(-se);
}
fenwick fw(disc.size());
sort(help.begin(),help.end(), [&cmp1](auto a, auto b) {return cmp1(get<0>(a),get<0>(b));});
sort(disc.begin(),disc.end(), cmp2);
int ans = 0;
for(auto [fi, se, tp]: help) {
int seNw = lower_bound(disc.begin(),disc.end(),se,cmp2) - disc.begin();
if(tp == 0)
fw.up(seNw, 1);
else
ans1[i][abs(tp)-1] += (tp>0?1:-1) * fw.qry(seNw);
}
}
for(int i=0;i<s;i++) {
vector<tuple<slope,slope,int>> help;
vector<slope> disc;
int f = spec[i];
for(auto [x, y]: dragon[f]) {
slope fi(x-d1,y-e1);
if(cmp1(-fi,fi))
fi = -fi;
slope se(x-d2,y-e2);
if(cmp2(-se,se))
se = -se;
help.push_back({fi, se, 0});
disc.push_back(se);
}
for(int g=0;g<m;g++)
if(g != f)
for(auto [x, y]: dragon[g]) {
slope fi(x-d1,y-e1);
slope se(x-d2,y-e2);
help.push_back({fi,se,g+1});
if(cmp1(-fi,fi))
help.push_back({-fi,se,-(g+1)});
if(cmp2(-se,se))
help.push_back({fi,-se,-(g+1)});
if(cmp1(-fi,fi)&&cmp2(-se,se))
help.push_back({-fi,-se,g+1});
disc.push_back(se);
disc.push_back(-se);
}
fenwick fw(disc.size());
sort(help.begin(),help.end(), [&cmp1](auto a, auto b) {return cmp1(get<0>(a),get<0>(b));});
sort(disc.begin(),disc.end(), cmp2);
int ans = 0;
for(auto [fi, se, tp]: help) {
int seNw = lower_bound(disc.begin(),disc.end(),se,cmp2) - disc.begin();
if(tp == 0)
fw.up(seNw, 1);
else
ans2[abs(tp)-1][i] += (tp>0?1:-1) * fw.qry(seNw);
}
}
int q;
cin >> q;
for(int f,g;q--;) {
cin >> f >> g;
f--; g--;
if(dragon[f].size() <= K && dragon[g].size() <= K) {
vector<tuple<slope,slope,int>> help;
vector<slope> disc;
for(auto [x, y]: dragon[g]) {
help.push_back({slope(x-d1,y-e1), slope(x-d2,y-e2), 0});
disc.push_back(slope(x-d2,y-e2));
}
for(auto [x, y]: dragon[f]) {
slope fi = slope(x-d1,y-e1);
if(cmp1(-fi,fi))
fi = -fi;
slope se = slope(x-d2,y-e2);
if(cmp2(-se,se))
se = -se;
help.push_back({fi, se, 1});
help.push_back({fi, -se, -1});
help.push_back({-fi, se, -1});
help.push_back({-fi, -se, 1});
disc.push_back(se);
disc.push_back(-se);
}
fenwick fw(disc.size());
sort(help.begin(),help.end(), [&cmp1](auto a, auto b) {return cmp1(get<0>(a),get<0>(b));});
sort(disc.begin(),disc.end(), cmp2);
int ans = 0;
for(auto [fi, se, tp]: help) {
int seNw = lower_bound(disc.begin(),disc.end(),se,cmp2) - disc.begin();
if(tp == 0)
fw.up(seNw, 1);
else
ans += tp * fw.qry(seNw);
}
cout << ans << "\n";
} else if(dragon[f].size() > K)
cout << ans1[lower_bound(spec.begin(),spec.end(),f)-spec.begin()][g] << "\n";
else
cout << ans2[f][lower_bound(spec.begin(),spec.end(),g)-spec.begin()] << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |