x轴上方给你n个点，m个水平杆子,
然后q组询问，每次询问一个点，问能看到多少个点。
n,q<=40000,m<=5
自闭了呀，又写了个 for(int i=1;i<(1<<m)-1;i++) 然后找了两个小时呀。
怎么这么强烈的即视感。。。
妙啊！这道题！太他妈的妙了啊！
我们注意到m很小，这不禁引起了我们的思考，把我头打断了也思考不出来啊，难道我们要枚举直线的子集？
考虑枚举子集，我们计算这个点，被这个子集中所有线段都能挡住的在x轴上的[l,r]这样的范围。
不能全挡住就丢掉。
对于所有的子集的L,R全存下来然后排个序。
然后我们对于一个查询，
也对所有的子集考虑这个范围，然后我们对这个[l,r]二分，
二分到的L的下标减去二分到的R的下标就是在覆盖了[l,r]的点的个数，
也就是对于这个子集，有这些点是不可视的。
然后进行简单容斥，奇数加，偶数减，就能得出来总的不可视的，
最后用n减去这个数就行了
妙啊！！！
怎么这么妙啊！
不需要什么乱七八糟的板子，一道绝妙的题！
1 // 2 // Created by gtx1080 on 2019-05-01. 3 // 4 #include <bits/stdc++.h> 5 #define pb push_back 6 using namespace std; 7 typedef double db; 8 const db eps = 1e-9; 9 const db pi = acos(-1); 10 int sign(db k){ 11 if (k>eps) return 1; else if (k<-eps) return -1; return 0; 12 } 13 int cmp(db k1,db k2){return sign(k1-k2);} 14 struct point { 15 db x,y; 16 point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};} 17 point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};} 18 point operator * (db k1) const{return (point){x*k1,y*k1};} 19 db abs2(){return x*x+y*y;} 20 }; 21 db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;} 22 db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;} 23 struct line{ 24 point p[2]; 25 line(point k1,point k2){p[0]=k1; p[1]=k2;} 26 point& operator [] (int k){return p[k];} 27 }; 28 int n,m,q,c[32]; 29 vector<line> l; 30 point p[40005]; 31 vector<line> w[32]; 32 vector<db> L[32],R[32]; 33 point inclux(point a,line b){ 34 return {a.x-(a.x-b[0].x)/(a.y-b[0].y)*a.y,a.x-(a.x-b[1].x)/(a.y-b[1].y)*a.y}; 35 } 36 point inter(point a,vector<line> b){//区间 37 point ret = {-1e18,1e18}; 38 for(auto x:b){ 39 point tmp = inclux(a,x); 40 ret.x = max(tmp.x,ret.x); 41 ret.y = min(tmp.y,ret.y); 42 } 43 return ret; 44 } 45 bool is_above(point p,vector<line> l){ 46 for(auto x:l)if(cmp(p.y,x[0].y)<=0)return false; 47 return true; 48 } 49 int slove(point q,int now){ 50 point cut = inter(q,w[now]); 51 if(cmp(cut.x,cut.y)<=0){ 52 int id1 = upper_bound(L[now].begin(),L[now].end(),cut.x+eps)-L[now].begin(); 53 int id2 = lower_bound(R[now].begin(),R[now].end(),cut.y-eps)-R[now].begin(); 54 return id1-id2; 55 } 56 return 0; 57 } 58 int main(){ 59 // freopen("/Users/gtx1080/Downloads/04.txt","r",stdin); 60 // freopen("/Users/gtx1080/Downloads/04.out","w",stdout); 61 scanf("%d%d%d",&n,&m,&q); 62 for(int i=1;i<=n;i++){ 63 scanf("%lf%lf",&p[i].x,&p[i].y); 64 } 65 db x1,x2,y; 66 for(int i=0;i<m;i++){ 67 scanf("%lf%lf%lf",&x1,&x2,&y); 68 l.pb(line({x1,y},{x2,y})); 69 } 70 for(int i=1;i<(1<<m);i++){ 71 c[i]=__builtin_popcount(i)%2==1?1:-1; 72 for(int j=0;j<m;j++) if(i&(1<<j))w[i].push_back(l[j]); 73 } 74 for(int i=1;i<(1<<m);i++){ 75 for(int j=1;j<=n;j++){ 76 if(is_above(p[j],w[i])){ 77 point cut = inter(p[j],w[i]); 78 if(cmp(cut.x,cut.y)<=0){ 79 L[i].push_back(cut.x); 80 R[i].push_back(cut.y); 81 } 82 } 83 } 84 sort(L[i].begin(),L[i].end()); 85 sort(R[i].begin(),R[i].end()); 86 } 87 // for(auto x:l)printf("%.11f %.11f %.11f ",x[0].x,x[1].x,x[0].y); 88 point x; 89 while (q--){ 90 scanf("%lf%lf",&x.x,&x.y); 91 int ans = 0; 92 for(int j=1;j<(1<<m);j++){ 93 ans+=c[j]*slove(x,j);//挡到的 94 } 95 ans=n-ans; 96 printf("%d ",ans); 97 } 98 }