102001 E

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减去这个数就行了

妙啊！！！

怎么这么妙啊！

不需要什么乱七八糟的板子，一道绝妙的题！

 //

 // Created by gtx1080 on 2019-05-01.

 //

 #include <bits/stdc++.h>

 #define pb push_back

 using namespace std;

 typedef double db;

 const db eps = 1e-;

 const db pi = acos(-);

 int sign(db k){

     if (k>eps) return ; else if (k<-eps) return -; return ;

 }

 int cmp(db k1,db k2){return sign(k1-k2);}

 struct point {

     db x,y;

     point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}

     point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}

     point operator * (db k1) const{return (point){x*k1,y*k1};}

     db abs2(){return x*x+y*y;}

 };

 db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}

 db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}

 struct line{

     point p[];

     line(point k1,point k2){p[]=k1; p[]=k2;}

     point& operator [] (int k){return p[k];}

 };

 int n,m,q,c[];

 vector<line> l;

 point p[];

 vector<line> w[];

 vector<db> L[],R[];

 point inclux(point a,line b){

     return {a.x-(a.x-b[].x)/(a.y-b[].y)*a.y,a.x-(a.x-b[].x)/(a.y-b[].y)*a.y};

 }

 point inter(point a,vector<line> b){//区间

     point ret = {-1e18,1e18};

     for(auto x:b){

         point tmp = inclux(a,x);

         ret.x = max(tmp.x,ret.x);

         ret.y = min(tmp.y,ret.y);

     }

     return ret;

 }

 bool is_above(point p,vector<line> l){

     for(auto x:l)if(cmp(p.y,x[].y)<=)return false;

     return true;

 }

 int slove(point q,int now){

     point cut = inter(q,w[now]);

     if(cmp(cut.x,cut.y)<=){

         int id1 = upper_bound(L[now].begin(),L[now].end(),cut.x+eps)-L[now].begin();

         int id2 = lower_bound(R[now].begin(),R[now].end(),cut.y-eps)-R[now].begin();

         return id1-id2;

     }

     return ;

 }

 int main(){

 //    freopen("/Users/gtx1080/Downloads/04.txt","r",stdin);

 //    freopen("/Users/gtx1080/Downloads/04.out","w",stdout);

     scanf("%d%d%d",&n,&m,&q);

     for(int i=;i<=n;i++){

         scanf("%lf%lf",&p[i].x,&p[i].y);

     }

     db x1,x2,y;

     for(int i=;i<m;i++){

         scanf("%lf%lf%lf",&x1,&x2,&y);

         l.pb(line({x1,y},{x2,y}));

     }

     for(int i=;i<(<<m);i++){

         c[i]=__builtin_popcount(i)%==?:-;

         for(int j=;j<m;j++) if(i&(<<j))w[i].push_back(l[j]);

     }

     for(int i=;i<(<<m);i++){

         for(int j=;j<=n;j++){

             if(is_above(p[j],w[i])){

                 point cut = inter(p[j],w[i]);

                 if(cmp(cut.x,cut.y)<=){

                     L[i].push_back(cut.x);

                     R[i].push_back(cut.y);

                 }

             }

         }

         sort(L[i].begin(),L[i].end());

         sort(R[i].begin(),R[i].end());

     }

 //    for(auto x:l)printf("%.11f %.11f %.11f\n",x[0].x,x[1].x,x[0].y);

     point x;

     while (q--){

         scanf("%lf%lf",&x.x,&x.y);

         int ans = ;

         for(int j=;j<(<<m);j++){

             ans+=c[j]*slove(x,j);//挡到的

         }

         ans=n-ans;

         printf("%d\n",ans);

     }

 }

巴特西

102001 E

最新文章

热门文章