【HDOJ1828&&POJ1177】Picture(线段树,扫描线)
2024-09-04 11:29:32
题意:给定n个矩形,求他们的并的周长
n<=5e3,abs(x[i])<=1e4
思路:From https://www.cnblogs.com/kuangbin/archive/2013/04/10/3013437.html
真实“线段”树
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 11000
#define M 7010
#define eps 1e-8
#define pi acos(-1)
#define oo 1e9
#define MOD 10007 struct node
{
int l,r,cnt,num,c;
bool lc,rc;
}t[N<<]; struct Line
{
int x1,x2,y,f;
}line[N]; bool cmp(Line a,Line b)
{
return a.y<b.y;
} int x[N]; void build(int l,int r,int p)
{
t[p].l=x[l];
t[p].r=x[r];
t[p].cnt=t[p].num=t[p].c=;
t[p].lc=t[p].rc=false;
if(l+==r) return;
int mid=(l+r)>>;
build(l,mid,p<<);
build(mid,r,p<<|);
} void calc(int p)
{
if(t[p].c>)
{
t[p].cnt=t[p].r-t[p].l;
t[p].num=;
t[p].lc=t[p].rc=true;
return;
}
if(t[p].l+==t[p].r)
{
t[p].cnt=t[p].num=;
t[p].lc=t[p].rc=false;
}
else
{
t[p].cnt=t[p<<].cnt+t[p<<|].cnt;
t[p].lc=t[p<<].lc;
t[p].rc=t[p<<|].rc;
t[p].num=t[p<<].num+t[p<<|].num;
if(t[p<<].rc&&t[p<<|].lc) t[p].num--;
}
} void update(int l,int r,Line e,int p)
{
if(t[p].l==e.x1&&t[p].r==e.x2)
{
t[p].c+=e.f;
calc(p);
return;
}
int mid=(l+r)>>;
if(e.x2<=t[p<<].r) update(l,mid,e,p<<);
else if(e.x1>=t[p<<|].l) update(mid,r,e,p<<|);
else
{
Line tmp=e;
tmp.x2=t[p<<].r;
update(l,mid,tmp,p<<);
tmp=e;
tmp.x1=t[p<<|].l;
update(mid,r,tmp,p<<|);
}
calc(p);
} int main()
{
//freopen("poj1177.in","r",stdin);
//freopen("poj1177.out","w",stdout);
int n;
while(scanf("%d",&n)!=EOF)
{
int cnt=;
for(int i=;i<=n-;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
line[cnt].x1=x1;
line[cnt].x2=x2;
line[cnt].y=y1;
line[cnt].f=;
x[cnt++]=x1;
line[cnt].x1=x1;
line[cnt].x2=x2;
line[cnt].y=y2;
line[cnt].f=-;
x[cnt++]=x2;
}
sort(line,line+cnt,cmp);
sort(x,x+cnt);
int m=unique(x,x+cnt)-x;
build(,m-,); int ans=;
int last=;
for(int i=;i<cnt-;i++)
{
update(,m-,line[i],); ans+=t[].num**(line[i+].y-line[i].y);
ans+=abs(t[].cnt-last);
last=t[].cnt;
}
update(,m-,line[cnt-],);
ans+=abs(t[].cnt-last);
printf("%d\n",ans);
} return ;
}
最新文章
- Oracle---------sql 中取值两列中值最大的一列
- C#相关
- html+css+javascript实现列表循环滚动示例代码
- 创建Java Web监听器
- redis window环境下的安装地址
- Repository模式介绍汇总
- Canvas 笔记(持续更新中)
- How to effectively work with multiple files in Vim?
- 什么时候用using (SPSite site = new SPSite(SPContext.Current.Web.Url))
- Oracle的卸载与安装
- 一道面试题与Java位操作 和 BitSet 库的使用
- javascript (十三) 函数
- React之组件通信
- 挑战常规--搭建gradle、maven私人仓库很简单
- 05-Mirrorgate数据库信息
- springMVC 使用WebApplicationContext获取ApplicationContext对象
- 使用CSS渐变
- Mysql添加字段.md
- Linux at 定时任务
- 下划线css