题意:给你n个坐标点，m个查询，每个查询有直线与x轴，y轴的交点坐标，然后让你求这 条直线经过几个坐标点
题解：用kdtree对n个点进行切割，然后如果直线与能包围该子树点的最小矩形没有交点那么这条直线肯定没有经过该子树任何一点
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<cstdio> #include<cmath> #include<set> #include<map> #include<cstdlib> #include<ctime> #include<stack> using namespace std; #define mes(a) memset(a,0,sizeof(a)) #define rep(i,a,b) for(i = a; i <= b; i++) #define dec(i,a,b) for(i = b; i >= a; i--) #define fi first #define se second #define ls rt<<1 #define rs rt<<1|1 #define mid (L+R)/2 #define lson ls,L,mid #define rson rs,mid+1,R typedef double db; typedef long long int ll; typedef pair<int,int> pii; typedef unsigned long long ull; const int mx = 1e5+5; const int x_move[] = {1,-1,0,0,1,1,-1,-1}; const int y_move[] = {0,0,1,-1,1,-1,1,-1}; int n,m; int flag; struct node{ int x,y; bool operator<(const node &a)const{ if(flag) return x<a.x; return y < a.y; } }a[mx]; struct kdtree{ int l,r; int u,d; void operator=(const node &a){ l = r = a.x; u = d = a.y; } kdtree operator+(const kdtree &a){ kdtree k; k.l = min(a.l,l); k.r = max(a.r,r); k.u = max(a.u,u); k.d = min(a.d,d); return k; } }kd[mx]; struct line{ ll a,b,c; line(line &x){ a = x.a; b = x.b; c = x.c; } line(ll x,ll y){ a = y,b = x,c = a*b; c = -c; } bool inr(kdtree k){ ll tmp = 1ll*a*k.l+c; tmp = -tmp; ll u = 1ll*k.u*b; ll d = 1ll*k.d*b; if(tmp>=d&&tmp<=u) return true; tmp = 1ll*a*k.r+c; tmp = -tmp; if(tmp>=d&&tmp<=u) return true; tmp = 1ll*b*k.u+c; tmp = -tmp; ll l = 1ll*k.l*a; ll r = 1ll*k.r*a; if(tmp>=l&&tmp<=r) return true; tmp = 1ll*b*k.d+c; tmp = -tmp; if(tmp>=l&&tmp<=r) return true; return false; } bool in(node t){ //if(t.x==2){ // cout<<a<<b<<c<<endl; // cout<<t.x*a+t.y*b+c<<endl; // } if(1ll*t.x*a+1ll*t.y*b+c==0) return true; return false; } }; void built(int L,int R,int dep,int fa){ if(L>R) return; flag = dep^1; nth_element(a+L,a+mid,a+R+1); kd[mid] = a[mid]; built(L,mid-1,dep^1,mid); built(mid+1,R,dep^1,mid); kd[fa] = kd[mid]+kd[fa]; } int query(int L,int R,line x){ if(L>R) return 0; if(!x.inr(kd[mid])) return 0; int ans = 0; if(x.in(a[mid])) ans++; if(L==R) return ans; return query(L,mid-1,x)+ans+query(mid+1,R,x); } int main(){ int t,q,ca = 1; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d%d",&a[i].x,&a[i].y); built(1,n,1,0); int x,y; while(m--){ scanf("%d%d",&x,&y); line l(x,y); printf("%d\n",query(1,n,l)); } } return 0; }