题解:题目比较明显的提示了二维数点,关键在于坐标的变换的推导,感觉是正常高中水平就可以推出,所以不在题解里赘述了(其实是画图太麻烦,懒的画)
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<b;i++) #define pb push_back #define db double #define ll long long #define fi first #define se second #define all(x) x.begin(),x.end() const db pi = acos(-1.0); const int N = 1e5+5; double eps = 1e-8; vector<pair<db,db> > point; struct Node{ db fi,se; int id; }; vector<Node> pt; vector<db> V; int res[N]; int C[N]; int lowbit(int x){return x&(-x);} int query(int x){ int t = 0; for(;x;x -= lowbit(x))t += C[x]; return t; } void mofidy(int x,int d){ for(;x<N;x+=lowbit(x))C[x]+=d; return; } int discrete(db x){ return lower_bound(all(V),x) - V.begin() + 1; } int main(){ int n,k; scanf("%d%d",&n,&k); point.resize(n); pt.resize(n); rep(i,0,n)scanf("%lf%lf",&point[i].fi,&point[i].se); while(k--){ V.clear(); memset(C,0,sizeof C); db l,r;scanf("%lf%lf",&l,&r); db sl = sinl(l/180.0*pi), cl = cosl(l/180.0*pi); db sr = sinl(r/180.0*pi), cr = cosl(r/180.0*pi); rep(i,0,n){ db & x = point[i].fi; db & y = point[i].se; pt[i].fi = x * sr + y * cr; pt[i].se = x * sl + y * cl; pt[i].id = i; V.pb(pt[i].se); } sort(all(V)); V.erase(unique(all(V),[&](db a,db b){return fabs(a-b) <= eps;}),V.end()); sort(all(pt),[&](Node a ,Node b){ return fabs(a.fi-b.fi)>eps?a.fi<b.fi:a.se>b.se; }); rep(i,0,n){ int yy = discrete(pt[i].second-eps); res[pt[i].id] += query(N-1) - query(yy-1); mofidy(yy,1); } } rep(i,0,n){ printf("%d ",res[i]); } printf("\n"); }