注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

矩形求并  

2009-09-13 10:17:30|  分类: 资料 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include<iostream>
#define  MAXL 5100
#define IN true
#define OUT false
using namespace std;
int y_li[MAXL*2];
int bs[MAXL*2];
int yl,bl;
struct tree_node
{
 int left,right,count;
 int length;
}tree[MAXL*8];
struct node
{
 int x,y1,y2;
 bool type;
}po[MAXL*2];
int pl;
int n;
int com(const void *p1,const void *p2)
{
 int q1=*(int *)p1;
 int q2=*(int *)p2;
 return q1-q2;
}
int com_point(const void *p1,const void *p2)
{
 node q1=*(node *)p1;
 node q2=*(node *)p2;
 return q1.x-q2.x;
}
int bsearch(int x)
{
 int left=1,right=bl-1,mid,temp;
 while(left<right)
 {
  mid=(left+right)>>1;
  temp=bs[mid]-x;
  if(temp==0)return mid;
  else if(temp>0) right=mid-1;
  else left=mid+1;
 }
 return left;
}
void build(int v,int left,int right)
{
 tree[v].count=0;tree[v].left=left;tree[v].right=right;
 if(right-left==1) return;
 int mid=(left+right)>>1;
 build(v<<1,left,mid);
 build((v<<1)+1,mid,right);
}
void insert(int v,int left,int right)
{
 if(tree[v].left==left&&tree[v].right==right)
 {
  tree[v].count++;
  tree[v].length=bs[right]-bs[left];
  return ;
 }
 int mid=(tree[v].left+tree[v].right)>>1;
 if(right<=mid) insert(v<<1,left,right);
 else if(left>=mid) insert((v<<1)+1,left,right);
 else
 {
  insert(v<<1,left,mid);
  insert((v<<1)+1,mid,right);
 }
 if(tree[v].count==0) tree[v].length=tree[v<<1].length+tree[(v<<1)+1].length;
}
void del(int v,int left,int right)
{
 if(tree[v].left==left&&tree[v].right==right)
 {
  tree[v].count-=1;
  if(tree[v].count==0)
  {
   if(tree[v].right==tree[v].left+1) tree[v].length=0.0;
   else tree[v].length=tree[v<<1].length+tree[(v<<1)+1].length;
  }
  return ;
 }
 int mid=(tree[v].left+tree[v].right)>>1;
 if(right<=mid) del(v<<1,left,right);
 else if(left>=mid) del((v<<1)+1,left,right);
 else
 {
  del(v<<1,left,mid);
  del((v<<1)+1,mid,right);
 }
 if(tree[v].count==0) tree[v].length=tree[v<<1].length+tree[(v<<1)+1].length;
}
int slove(int x)
{
  int i,tt,left,right;
 int t1,t2,t3,t4,ans,pre;
  pl=0;yl=0;

n=x;
  for(i=0;i<n;i++)
  {
   po[pl].x=t1;po[pl].y1=t2;po[pl].y2=t4;po[pl].type=IN;pl++;//更改输入输出
   po[pl].x=t3;po[pl].y1=t2;po[pl].y2=t4;po[pl].type=OUT;pl++;//更改输入输出
   y_li[yl++]=t2;y_li[yl++]=t4;
  }
  if(i==0) break;
  qsort(y_li,yl,sizeof(y_li[0]),com);
  bl=1;
  bs[bl++]=y_li[0];
  for(i=1;i<yl;i++)
  {
   if(y_li[i]!=y_li[i-1]) bs[bl++]=y_li[i];
  }
  build(1,1,bl-1);
  ans=0;
  pre=0;
  qsort(po,pl,sizeof(po[0]),com_point);
  for(i=0;i<pl;i++)
  {
   left=bsearch(po[i].y1);
   right=bsearch(po[i].y2);
   if(po[i].type==IN) insert(1,left,right);   
   else del(1,left,right);
   if(i>0)ans+=(po[i].x-po[i-1].x)*pre;
   pre=tree[1].length;
  }

return ans;
}

  评论这张
 
阅读(101)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017