概述
参考
http://wenku.baidu.com/view/1856cf84b9d528ea81c77918.html
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<cmath>
#define L(x) (x<<1)
#define R(x) (x<<1 |1)
#define MAX 5010
using namespace std;
int cy[2*MAX];
int m1,m2;
class seg
{
public:
int x,y1,y2,f;
seg(){};
seg(int a,int b,int c,int d):x(a),y1(b),y2(c),f(d)
{}
bool operator< (const seg b)const
{
return x<b.x;
}
}line[MAX*2];
struct node
{
int l,r,length,cover;
int num;
int cr,cl;
}a[2*MAX];
void build(int t,int l,int r)
{
a[t].l=l;
a[t].r=r;
a[t].cover=0;
a[t].length=0;
a[t].cr=0;
a[t].cl=0;
a[t].num=0;
if(r-l==1)return ;
int mid=(l+r)/2;
build(L(t),l,mid);
build(R(t),mid,r);
}
int ll=0;
void uplen(int t)
{
if(a[t].cover>0)
{
a[t].length=cy[a[t].r]-cy[a[t].l];
a[t].num=1;
a[t].cr=1;
a[t].cl=1;
}
else
if(a[t].r-a[t].l==1)
{
a[t].length=0;
a[t].cr=0;
a[t].cl=0;
a[t].num=0;
}
else
{
a[t].cl=a[L(t)].cl;
a[t].cr=a[R(t)].cr;
a[t].num=a[L(t)].num+a[R(t)].num-a[L(t)].cr*a[R(t)].cl;
a[t].length=a[L(t)].length+a[R(t)].length;
}
}
void update(int t ,seg s)
{
if(cy[a[t].l]>=s.y1&&cy[a[t].r]<=s.y2)
{
a[t].cover+=s.f;
uplen(t);
return;
}
if(a[t].r-a[t].l==1)return ;
int mid=(a[t].l+a[t].r)/2;
if(s.y1<=cy[mid])
update(L(t),s);
if(s.y2>=cy[mid])
update(R(t),s);
uplen(t);
}
void addlen(int x1,int x2,int y1,int y2)
{
line[m1++]=seg(x1,y1,y2,1);
line[m1++]=seg(x2,y1,y2,-1);
cy[m2++]=y1;
cy[m2++]=y2;
}
int main()
{
int x1,x2,y1,y2;
int l1,l2;
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
m1=0;
m2=0;
ll=0;
l1=0;
l2=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
addlen(x1,x2,y1,y2);
}
sort(line,line+m1);
sort(cy,cy+m2);
m2=unique(cy,cy+m2)-cy;
build(1,0,m2-1);
for(i=0;i<m1;i++)
{
update(1,line[i]);
ll+=abs(a[1].length-l1);
if(i<m1-1)
{
ll+=2*a[1].num*(line[i+1].x-line[i].x);
}
l1=a[1].length;
}
printf("%dn",ll);
}
}
最后
以上就是轻松海燕为你收集整理的poj1177的全部内容,希望文章能够帮你解决poj1177所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复