#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MAXN = 3e4+1, MAXQ = 1e5+1;
int n, m, t[MAXN], q, ans[MAXQ];
int sgn(ll x) {
return (x>=0)?x? 1: 0: -1;
}
struct Point {
int x, y;
int id;
Point() {}
Point(int _x, int _y): x(_x), y(_y) {}
void read() { cin>>x>>y; }
Point operator-(const Point& o) const { return Point(x-o.x, y-o.y); }
bool operator<(const Point& o) const { return make_pair(x, y) < make_pair(o.x, o.y); }
ll cross(const Point& o) {
return (ll)x*o.y - (ll)y*o.x;
}
ll cross(const Point& o1, const Point& o2) {
return (o1 - *this).cross(o2 - *this);
}
};
Point O1, O2;
bool cmp(Point p1, Point p2) { // clockwise
if(sgn(O1.cross(O2, p1)) != sgn(O1.cross(O2, p2))) {
return (O1.cross(O2, p1) < 0LL)? true : false;
}
return O1.cross(p1, p2) < 0LL;
}
Point p[MAXN], pp[MAXN], s[MAXN];
vector<int> tribe[MAXN];
vector<pair<Point, int>> queries[MAXN];
int bit[MAXN];
void add(int idx, int delta) {
assert(idx >= 0);
for(; idx < n; idx = idx | (idx+1)) {
bit[idx] += delta;
}
}
int sum(int r) {
assert(r >= 0);
int res = 0;
for(; r>=0; r = (r & (r+1)) - 1) {
res += bit[r];
}
return res;
}
int sum(int l, int r) {
return sum(r) - ((l>0)?sum(l-1): 0);
}
void solve(vector<Point> pts, vector<pair<Point, int>> qs) {
sort(pts.begin(), pts.end());
sort(qs.begin(), qs.end());
int j = 0;
for(int i=0; i<(int)pts.size(); ++i) {
while(j < (int)qs.size() && qs[j].st < pts[i]) {
ans[qs[j].nd] += sum(0, qs[j].st.y-1);
j++;
}
add(pts[i].y-1, 1);
}
while(j < (int)qs.size()) {
ans[qs[j].nd] += sum(0, qs[j].st.y-1);
j++;
}
for(int i=0; i<(int)pts.size(); ++i) {
add(pts[i].y-1, -1);
}
}
Point reflect(Point pt, Point o) {
int dx = o.x - pt.x, dy = o.y - pt.y;
pt.x += 2*dx, pt.y += 2*dy;
return pt;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1; i<=n; ++i) {
p[i].read();
p[i].id = i;
cin>>t[i];
tribe[t[i]].push_back(i);
}
Point P1, P2;
P1.read(), P2.read();
if(P2 < P1) swap(P1, P2);
for(int i=1; i<=n; ++i) {
if(P1.cross(P2, p[i]) > 0LL) {
pp[i] = reflect(p[i], P1);
}
else {
pp[i] = p[i];
}
}
O1 = P1, O2 = P2;
sort(pp+1, pp+n+1, cmp);
for(int i=1; i<=n; ++i) {
s[pp[i].id].x = i;
}
for(int i=1; i<=n; ++i) {
if(P2.cross(P1, p[i]) < 0LL) {
pp[i] = reflect(p[i], P2);
}
else {
pp[i] = p[i];
}
}
O1 = P2, O2 = P1;
sort(pp+1, pp+n+1, cmp);
for(int i=1; i<=n; ++i) {
s[pp[i].id].y = i;
}
cin>>q;
for(int i=1; i<=q; ++i) {
int a, b; cin>>a>>b;
if(tribe[a].size() > tribe[b].size()) {
for(auto j: tribe[b]) {
queries[b].push_back(mp(s[j], -i));
}
}
else {
for(auto j: tribe[a]) {
queries[b].push_back(mp(s[j], i));
}
}
}
for(int i=1; i<=m; ++i) {
vector<Point> up, down, up_r, down_r;
vector<pair<Point, int>> upq, downq, upq_r, downq_r;
for(auto j: tribe[i]) {
if(P1.cross(P2, p[j]) < 0LL) {
down.push_back(Point(s[j].x, n-s[j].y+1));
down_r.push_back(Point(n-s[j].x+1, s[j].y));
}
else {
up.push_back(Point(n-s[j].x+1, s[j].y));
up_r.push_back(Point(s[j].x, n-s[j].y+1));
}
}
for(auto j: queries[i]) {
if(j.nd > 0) {
upq.push_back(mp(Point(n-j.st.x+1, j.st.y), j.nd));
downq.push_back(mp(Point(j.st.x, n-j.st.y+1), j.nd));
}
else {
if(P1.cross(P2, j.st) > 0LL) {
upq_r.push_back(mp(Point(j.st.x, n-j.st.y+1), -j.nd));
downq.push_back(mp(Point(j.st.x, n-j.st.y+1), -j.nd));
}
else {
upq.push_back(mp(Point(n-j.st.x+1, j.st.y), -j.nd));
downq_r.push_back(mp(Point(n-j.st.x+1, j.st.y), -j.nd));
}
}
}
solve(up, upq);
solve(down, downq);
solve(up_r, upq_r);
solve(down_r, downq_r);
}
for(int i=1; i<=q; ++i) {
cout<<ans[i]<<'\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
2156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
43 ms |
4764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
2156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
