首页 > 代码库 > sgu316Kalevich Strikes Back（线段树+扫描线）

sgu316Kalevich Strikes Back（线段树+扫描线）

2024-07-07 09:22:06   225人阅读

做法：总体想法是求出一个矩形的面积以及它所包含的矩形，然后用自己的面积减掉所包含的。主要问题是怎样求解它所包含的矩形。

因为是没有相交点的，可以利用扫描线的方法去做，类似染色，当前段如果是x色，也就是第x个矩形，那么再把他染成y颜色时，说明x包含y，而当扫到y的上边时，这一段又恢复到x色。标记一下被包含的矩形，记录所包含的矩形。

因为会有恢复染色操作，up需要时时更新，左儿子和右儿子一样颜色时就可以合并为一段。

  1 ;
  2 }
  3 void down(int w)
  4 {
  5     if(s[w]!=-1)
  6     {
  7         s[w<<1] = s[w<<1|1] = s[w];
  8         s[w] = -1;
  9     }
 10 }
 11 void build(int l,int r,int w)
 12 {
 13     s[w] = 0;
 14     if(l==r)
 15     {
 16         return ;
 17     }
 18     int m = (l+r)>>1;
 19     build(l,m,w<<1);
 20     build(m+1,r,w<<1|1);
 21     up(w);
 22 }
 23 int update(int a,int b,int d,int l,int r,int w)
 24 {
 25     if(a<=l&&b>=r)
 26     {
 27         int k = s[w];
 28        // cout<<l<<" "<<r<<" "<<s[w]<<endl;
 29         s[w] = d;
 30         return k;
 31     }
 32     down(w);
 33     int m  = (l+r)>>1;
 34     int k = 0;
 35     if(a<=m)
 36     k = update(a,b,d,l,m,w<<1);
 37     if(b>m)
 38     k = update(a,b,d,m+1,r,w<<1|1);
 39     up(w);
 40     return k;
 41 }
 42 int main()
 43 {
 44     int n,w,h,i,j;
 45     scanf("%d%d%d",&n,&w,&h);
 46     int g = 0;
 47     for(i = 1;i <= n; i++)
 48     {
 49         int x1,x2,y1,y2;
 50         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
 51         p[++g] = node(x1,x2,min(y1,y2),i);
 52         a[g] = x1;
 53         p[++g] = node(x1,x2,max(y1,y2),-i);
 54         a[g] = x2;
 55         sum[i] = (LL)abs(x1-x2)*abs(y1-y2);
 56     }
 57     sort(p+1,p+g+1);
 58     sort(a+1,a+g+1);
 59     int o = 0;
 60     f[a[1]] = ++o;
 61     for(i = 2; i <= g;i++)
 62     {
 63         if(a[i]!=a[i-1])
 64         {
 65             f[a[i]] = ++o;
 66             val[o] =a[i];
 67         }
 68     }
 69     build(1,o,1);
 70     for(i = 1; i <= g;i++)
 71     {
 72         int l = min(f[p[i].x1],f[p[i].x2]);
 73         int r = max(f[p[i].x2],f[p[i].x1]);
 74         //cout<<l<<" "<<r<<endl;
 75         if(l<=r)
 76         {
 77             if(p[i].d>0)
 78             {
 79                 int k = update(l,r,p[i].d,1,o,1);
 80                 ed[k].push_back(p[i].d);
 81                 pre[p[i].d] = k;
 82                 //cout<<k<<" "<<p[i].d<<endl;
 83             }
 84             else
 85             {
 86                 update(l,r,pre[-p[i].d],1,o,1);
 87             }
 88             //fresh(l,r,1,o,1);
 89         }
 90     }
 91     sum[0] =(LL)w*h;
 92     for(i = 0 ;i <= n; i++)
 93     ans[i] = sum[i];
 94     for(i = 0; i <= n; i++)
 95     {
 96         for(j = 0 ;j < ed[i].size() ; j++)
 97         {
 98             int v = ed[i][j];
 99             ans[i]-=sum[v];
100         }
101     }
102     sort(ans,ans+n+1);
103     for(i = 0 ;i < n; i++)
104     printf("%I64d ",ans[i]);
105     printf("%I64d\n",ans[n]);
106     return 0;
107 }
View Code

 

 


联系
我们