你最愿意做的哪件事，才是你的天赋所在

0%

基础计算几何-扫描线

发表于 Valine：

扫描线

这个算法就是求二维平面上n个矩形覆盖的面积之和，我们用扫描线来解决。
oi_wiki中的图示说明的很明白
扫描线
我们用线段树维护的就是当前的仍剩余的长度，就是从下至上的那条线的长度。
把线按从y轴小到大排序，然后不停的插入线段树中，并且入边则+1，出边则-1；

扫描线求面积

HDU 1524
这题需要离散化，因为边有小数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 3e2+10;
struct node
{
	double l,r;
	double sum;
	int lazy;
}tree[N<<3];
struct Point{
	double x,y;
};
bool syn(double x)
{
	if(fabs(x)<1e-12)return 0;
	return x>0?1:-1;
}
struct line{
	Point s,t;
	int flag;
	bool operator < (const line a)const
	{
		if(s.y!=a.s.y)return s.y<a.s.y;
		return s.x<a.s.x;
	}
}l[N<<3];
double s[N<<3];
void PushUp(int rt)
{
	if(tree[rt].lazy>0)
	{
		tree[rt].sum=tree[rt].r-tree[rt].l;
	}
	else
	{
		tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
	}
}
void build(int l,int r,int rt)
{
	if(r-l>1)
	{
		tree[rt].l=s[l];
		tree[rt].r=s[r];
		build(l,(l+r)/2,rt*2);
		build((l+r)/2,r,rt*2+1);
		PushUp(rt);
	}
	else
	{
		tree[rt].l=s[l];
		tree[rt].r=s[r];
		tree[rt].sum=0;
	}
	return ;
}
void Update(int rt, double x1,double x2,int flag)
{
	if(tree[rt].l>=x1&&tree[rt].r<=x2)
	{
		
		tree[rt].lazy += flag;
		PushUp(rt);
		return ;
	}
	if(tree[rt<<1].r>x1)Update(rt<<1,x1,x2,flag);
	if(tree[rt<<1|1].l<x2)Update(rt<<1|1,x1,x2,flag);
	PushUp(rt);
}
int main()
{
	int n;
	int cas=1;
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
		double x1,x2,y1,y2,ans=0;
		for(int i=0;i<n;i++)
		{
			scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
			l[i].s.x=x1;l[i].s.y=y1;l[i].flag=1;
			l[i].t.x=x2;l[i].t.y=y1;
			l[i+n].s.x=x1;l[i+n].s.y=y2;l[i+n].flag=-1;
			l[i+n].t.x=x2;l[i+n].t.y=y2;
			s[i+1]=x1;
			s[i+n+1]=x2;
		}
		for(int i=0;i<N<<3;i++)tree[i].lazy=0;
		sort(s+1,s+2*n+1);//离散化边，然后就可以建树了 
		build(1,2*n,1);
		sort(l,l+2*n);
		Update(1,l[0].s.x,l[0].t.x,1);
		for(int i=1;i<2*n;i++)
		{
			ans+=(l[i].s.y-l[i-1].s.y)*tree[1].sum;
			Update(1,l[i].s.x,l[i].t.x,l[i].flag);
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n", cas++, ans);
	}
 }

扫描线求周长

HDU1828
扫描线求周长与面积的思想类似，不同的地方在于求竖线的时候，需要求当前区间内存在多少段线段，维护这个值就可以求了；
例如[1,10]之中有[1,2],[4,5]就有两段线段，那么竖的长度就为2段数(y-y`)。
并且在节点中需要维护lc,rc判断线段两端是否被覆盖，以及s，覆盖的次数即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e4+10; 
struct node
{
	int l,r,len,s,lc,rc,num;
}tree[N<<2];
void PushUp(int rt)
{
	if(tree[rt].s)
	{
		tree[rt].len=tree[rt].r-tree[rt].l+1;
		tree[rt].lc=tree[rt].rc=1;
		tree[rt].num=1;
	}
	else if(tree[rt].r==tree[rt].l)
	{
		tree[rt].len=0;
		tree[rt].lc=tree[rt].rc=0;
		tree[rt].num=0;
	}
	else {
		tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
		tree[rt].lc=tree[rt<<1].lc;
		tree[rt].rc=tree[rt<<1|1].rc;
		tree[rt].num=tree[rt<<1].num+tree[rt<<1|1].num-(tree[rt<<1].rc&tree[rt<<1|1].lc);
	}
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		tree[rt].l=tree[rt].r=l;
		tree[rt].lc=tree[rt].rc=tree[rt].num=tree[rt].s=0;
		return ;
	}
	else
	{
		tree[rt].l=l;
		tree[rt].r=r;
		tree[rt].lc=tree[rt].rc=tree[rt].num=tree[rt].s=0;
		build(l,(l+r)/2,rt<<1);
		build((l+r)/2+1,r,rt<<1|1);
	}
}
void Update(int rt,int x1,int x2,int flag)
{
	if(x1>tree[rt].r||x2<tree[rt].l)return ;
	if(x1<=tree[rt].l&&x2>=tree[rt].r)
	{
		tree[rt].s+=flag;
		PushUp(rt);
		return ; 
	}
	int mid = (tree[rt].l+tree[rt].r)>>1;
	Update(rt<<1,x1,x2,flag);
	Update(rt<<1|1,x1,x2,flag);
	PushUp(rt);
}
struct Point{
	int x1,x2,y,flag;
}p[N]; 
bool cmp(Point a,Point b){
	if(a.y!=b.y)return a.y<b.y;
	return a.x1<b.x1;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF&&n)
	{
	
	int cnt = 1,ans=0;
	int minn = 9999999;
	int maxx  = -9999999;
    for(int i=0;i<n;i++)
	{
		int x1,x2,y1,y2;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		x1+=10010;y1+=10010;x2+=10010;y2+=10010;
		maxx=max(maxx,max(x1,x2));
		minn=min(minn,min(x1,x2));
		p[i].x1=x1;p[i].x2=x2;p[i].y=y1;p[i].flag=1;
		p[i+n].x1=x1;p[i+n].x2=x2;p[i+n].y=y2;p[i+n].flag=-1;
	}
	int last = 0;
	build(minn-1,maxx+1,1);
	sort(p,p+2*n,cmp);
	for(int i=0;i<2*n;i++)
	{
		Update(1,p[i].x1,p[i].x2-1,p[i].flag);
		if(i!=2*n-1)
		ans+=2*tree[1].num*(p[i+1].y-p[i].y);
		ans+=abs(tree[1].len-last);
		last = tree[1].len;
	}
	printf("%d\n",ans);
   }
}

HDU-3265

扫描线板子题，思路是把一个矩形拆成四个矩形

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 65555;
struct node
{
	int l,r,lazy,sum;
}tree[N<<2];
void build(int l,int r,int rt)
{
	if(l==r)
	{
		tree[rt].l=tree[rt].r=r;
		tree[rt].sum=0;
		tree[rt].lazy=0;
		return ;
	} 
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].lazy=tree[rt].sum=0;
	build(l,(l+r)/2,rt<<1);
	build((l+r)/2+1,r,rt<<1|1);
}
void PushUp(int rt)
{
	if(tree[rt].lazy)
	{
		tree[rt].sum=tree[rt].r-tree[rt].l+1;
	}
	else if(tree[rt].l==tree[rt].r)tree[rt].sum=0;
	else tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void Update(int rt,int l,int r,int flag)
{
	if(l<=tree[rt].l&&tree[rt].r<=r)
	{
		tree[rt].lazy+=flag;
		PushUp(rt);
		return ;
	}
	int mid = (tree[rt].l+tree[rt].r)>>1;
	if(l<=mid)Update(rt<<1,l,r,flag);
	if(mid<r)Update(rt<<1|1,l,r,flag);
	PushUp(rt);
}
struct line{
	int x1,x2,y,flag;
	line(){}
	line(int a,int b,int c,int d){
		x1=a;
		x2=b;
		y=c;
		flag = d;
	}
}nodes[N*8];
int cmp(line a,line b)
{
	if(a.y==b.y)return a.flag>b.flag;
	return a.y<b.y;
}
int main(){
   int n;
   while(scanf("%d",&n)!=EOF&&n!=0)
   {  int x1,x2,x3,x4,y1,y2,y3,y4;
    ll ans=0;
      int minn = 50000;
      int maxx = 0;
      int m = 0;
   	  for(int i=0;i<n;i++)
   	  {
   	  	scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
   	        nodes[++m]= line(x1,x3,y1,1);
            nodes[++m]= line(x1,x3,y2,-1);
            nodes[++m]= line(x4,x2,y1,1);
            nodes[++m]= line(x4,x2,y2,-1);
            nodes[++m]= line(x3,x4,y1,1);
            nodes[++m]= line(x3,x4,y3,-1);
            nodes[++m]= line(x3,x4,y4,1);
            nodes[++m]= line(x3,x4,y2,-1);
   	  	minn=min(minn,x1);
   	  	maxx=max(maxx,x2);
	  }
	  sort(nodes+1,nodes+m+1,cmp);
	  build(minn,maxx-1,1);
	  for(int i=1;i<m;i++)
	  {
	  	int ql=nodes[i].x1;
        int qr=nodes[i].x2-1;
        //printf("%d %d %d\n",ql,qr,tree[1].sum);
        if(ql<=qr)Update(1,ql,qr,nodes[i].flag);//update(ql,qr,nodes[i].d,1,lbd,rbd-1);
        ans+= (long long)tree[1].sum*(nodes[i+1].y-nodes[i].y); 
	  }
	  printf("%I64d\n",ans);
	}	
}
-------------你最愿意做的哪件事才是你的天赋所在-------------