对于扫描线的原理可以依靠以下的图片很好的理解
对于逐层计算当前的面积 利用线段树维护每一时刻的底长 乘上 每一段的高h
以下图转载自@kk303
HDU1542Atlantis 矩形面积并
题目链接
题目大意
求若干个矩阵的面积并
题目思路
由于给出的点都是double类型需要离散化每个x坐标
然后是对于线段树的建树和维护操作 每次维护更新sum【1】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
struct xy{int cnt;double sum;int v,add,mul=1;
}ans[maxn<<1];
struct node{double l,r,h;int d;bool operator<(const node &x)const {return h<x.h;}
}a[maxn*2];
int n,m;
double all[maxn*2];
int ls(int x)
{return x<<1;
}
int rs(int x)
{return x<<1|1;
}
void pushup(int x,int l,int r)
{if(ans[x].cnt)ans[x].sum=all[r+1]-all[l];//每一个节点是一个块而数组代表的值是每一个块左端点 else if(l==r) ans[x].sum=0;else ans[x].sum=ans[ls(x)].sum+ans[rs(x)].sum;
}
void bt(int x,int l,int r)
{ans[x].cnt=0;ans[x].sum=0.0;if(l==r){ans[x].cnt=0;ans[x].sum=0.0;return ;}int mid=(l+r)/2;bt(ls(x),l,mid);bt(rs(x),mid+1,r);pushup(x,l,r);
}
void updata(int l,int r,int nl,int nr,int x,int k)
{//if(nl<nr)pushdown(x,nl,nr);int mid=(nl+nr)/2;if(nl>=l&&nr<=r){ans[x].cnt+=k;pushup(x,nl,nr);return ;}//pushdown(x,nl,nr);if(mid>=l){updata(l,r,nl,mid,ls(x),k);}if(mid<r){updata(l,r,mid+1,nr,rs(x),k);}pushup(x,nl,nr);}
int main()
{int kase=0;while(cin>>n){if(n==0)break;for(int i=1;i<=n;i++){double x1,x2,y1,y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);a[i].l=x1;a[i].r=x2;a[i].h=y1;a[i].d=1;a[i+n].l=x1;a[i+n].r=x2;a[i+n].h=y2;a[i+n].d=-1;all[i]=x1;all[i+n]=x2;}sort(a+1,a+2*n+1);sort(all+1,all+2*n+1);n*=2;int m=unique(all+1,all+n+1)-all-1;//memset(cnt, 0, sizeof cnt);//memset(sum, 0, sizeof sum);bt(1,1,m);double anss=0;for(int i=1;i<n;i++){int l=lower_bound(all+1,all+m+1,a[i].l)-all;int r=lower_bound(all+1,all+m+1,a[i].r)-all;if(l<r)updata(l,r-1,1,m,1,a[i].d);anss+=ans[1].sum*(a[i+1].h-a[i].h);}printf("Test case #%d\nTotal explored area: %.2f\n\n", ++kase, anss);}return 0;
}HDU-1255覆盖的面积 矩阵面积交
题目链接
题目大意
求矩阵交
题目思路
用tree结构体里的cnt代表 这一层里该部分出现了几次 two代表出现了两次以上的答案 one 代表出现了一次以上的答案
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
struct xy{int cnt;double two,one;int v,add,mul=1;
}ans[maxn<<1];
struct node{double l,r,h;int d;bool operator<(const node &x)const {return h<x.h;}
}a[maxn*2];
int n,m;
double all[maxn*2];
int ls(int x)
{return x<<1;
}
int rs(int x)
{return x<<1|1;
}
void pushup(int x,int l,int r)
{if(ans[x].cnt>=2){ans[x].two=ans[x].one=all[r+1]-all[l];}else if(ans[x].cnt==1){ans[x].one=all[r+1]-all[l];if(l==r)ans[x].two=0;else ans[x].two=ans[ls(x)].one+ans[rs(x)].one;}else {if(l==r)ans[x].two=ans[x].one=0;else {ans[x].two=ans[ls(x)].two+ans[rs(x)].two;ans[x].one=ans[ls(x)].one+ans[rs(x)].one;}}}
void bt(int x,int l,int r)
{ans[x].cnt=0;ans[x].two=ans[x].one=0.0;if(l==r){ans[x].cnt=0;ans[x].two=ans[x].one=0.0;return ;}int mid=(l+r)/2;bt(ls(x),l,mid);bt(rs(x),mid+1,r);pushup(x,l,r);
}
void updata(int l,int r,int nl,int nr,int x,int k)
{//if(nl<nr)pushdown(x,nl,nr);int mid=(nl+nr)/2;if(nl>=l&&nr<=r){ans[x].cnt+=k;pushup(x,nl,nr);return ;}//pushdown(x,nl,nr);if(mid>=l){updata(l,r,nl,mid,ls(x),k);}if(mid<r){updata(l,r,mid+1,nr,rs(x),k);}pushup(x,nl,nr);}
int main()
{int T;cin>>T;while(T--){cin>>n;//if(n==0)break;for(int i=1;i<=n;i++){double x1,x2,y1,y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);a[i].l=x1;a[i].r=x2;a[i].h=y1;a[i].d=1;a[i+n].l=x1;a[i+n].r=x2;a[i+n].h=y2;a[i+n].d=-1;all[i]=x1;all[i+n]=x2;}sort(a+1,a+2*n+1);sort(all+1,all+2*n+1);n*=2;int m=unique(all+1,all+n+1)-all-1;//memset(cnt, 0, sizeof cnt);//memset(sum, 0, sizeof sum);bt(1,1,m);double anss=0;for(int i=1;i<n;i++){int l=lower_bound(all+1,all+m+1,a[i].l)-all;int r=lower_bound(all+1,all+m+1,a[i].r)-all;if(l<r)updata(l,r-1,1,m,1,a[i].d);anss+=ans[1].two*(a[i+1].h-a[i].h);}//cout<<anss<<endl; printf("%.2lf\n", anss);}return 0;
}H-Hopping Rabbit
链接：https://ac.nowcoder.com/acm/contest/11257/H
来源：牛客网
题目描述
Little Rabbit loves hopping. He always hops around on the grassland. But dangers are lurking there --- the hunters have set nnn traps. Once Little Rabbit falls into a trap, his life will be threatened. Therefore, Little Rabbit has to keep away from those traps.
Let's use two-dimensional Cartesian coordinate system to describe the grassland. We can regard Little Rabbit as a point, and regard traps as rectangles on the plane. The sides of the rectangles are parallel to the coordinate axes. We use two points to describe a rectangle --- the lower left point (x1,y1)(x_1,y_1)(x1?,y1?) and the upper right point (x2,y2)(x_2,y_2)(x2?,y2?) (x1<x2x_1<x_2x1?<x2?, y1<y2y_1<y_2y1?<y2?, x1,y1,x2,y2x_1,y_1,x_2,y_2x1?,y1?,x2?,y2? are all integers).
Little Rabbit can hop in the direction of xxx-axis or yyy-axis. The length of each hop is ddd. Formally, if Little Rabbit locates at (x,y)(x,y)(x,y), he can then hop to (x?d,y)(x-d,y)(x?d,y), (x+d,y)(x+d,y)(x+d,y), (x,y?d)(x,y-d)(x,y?d) or (x,y+d)(x,y+d)(x,y+d).
Little Rabbit wants to find an initial position (x0+0.5,y0+0.5)(x_0+0.5,y_0+0.5)(x0?+0.5,y0?+0.5) (x0x_0x0? and y0y_0y0? are integers) so that when he starts to hop from this point, no matter how he hops, he will never fall into a trap. Please help Little Rabbit to find such a point.
Please note that during a hop, Little Rabbit is in the air and won't fall into a trap. Little Rabbit will fall into a trap only if his landing point is in a trap.
输入描述:
The first line contains two integers nnn and ddd (1≤n,d≤1051 \le n,d \le 10^51≤n,d≤105) --- the number of traps and the length of each hop.
Then in the next nnn lines, each line contains four integers x1,y1,x2,y2x_1,y_1,x_2,y_2x1?,y1?,x2?,y2? (?109≤x1,y1,x2,y2≤109-10^{9} \le x_1,y_1,x_2,y_2 \le 10^{9}?109≤x1?,y1?,x2?,y2?≤109, x1<x2x_1<x_2x1?<x2?, y1<y2y_1<y_2y1?<y2?) --- the lower left point and the upper right point of the rectangle.
It's possible that the rectangles will intersect with each other.
输出描述:
If there exist valid answers, output YES in the first line. Then output two integers x0,y0x_0,y_0x0?,y0? (?109≤x0,y0≤109-10^{9} \le x_0,y_0 \le 10^{9}?109≤x0?,y0?≤109) separated by a space in the second line, indicating a valid initial position (x0+0.5,y0+0.5)(x_0+0.5,y_0+0.5)(x0?+0.5,y0?+0.5). If there are multiple answers, output any.
If there are no valid answers, output NO in a single line.
题目大意
平面上有 n 个矩形，给定d，需要找到一个位置 (x,y)，使得所有 (x+kd,y+kd) 均不落在矩形中。
题目思路
由于能到的位置是周期重复的，我们可以将所有 (k_1d,k_2d) 到 (k_1d+d,k_2d+d) 范围内的图形移动至 (0,0) 到 (d,d) 范围内求并。如果说最终 (0,0) 到 (d,d) 的范围内没有被完全覆盖，那么小兔从没有被覆盖到的点出发即可。如果被完全覆盖了，那么就没有合法的答案。
这个问题最终可以转化成将 n 个矩形移动至 (0,0) 到 (d,d) 范围内求并，是扫描线的典型应用。根据矩形的位置和大小，将其移动至 (0,0) 到 (d,d) 范围内时可能会拆成 2 甚至 4 个矩形。由于此题需要输出方案，我们可以在线段树上维护一个覆盖次数的最小值，当扫描到某一行发现最小值为 0 时，说明这一行存在某个位置没有被覆盖完全，然后枚举这一行所有位置找到覆盖次数为 0 的即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf =0x3f3f3f3f;
const int maxn=2e5+10;
int n,d;
vector<pair<int,int> > add[maxn],del[maxn];
struct xy{int v,add,mul=1;//mul没有用到 套的之前的板子
}ans[maxn<<2];
int ls(int x)
{return x<<1;
}
int rs(int x)
{return x<<1|1;
}
void pushup(int x)
{ans[x].v=min(ans[ls(x)].v,ans[rs(x)].v);//ans[x].v%=p;
}
void bt(int x,int l,int r)
{ans[x].add=0;ans[x].mul=1;if(l==r){ans[x].v=0;//ans[x].v%=p;return ;}int mid=(l+r)/2;bt(ls(x),l,mid);bt(rs(x),mid+1,r);pushup(x);
}
void pushdown(int x,int l,int r)
{//ll mid=(l+r)/2;//根据我们规定的优先度，//儿子的值=此刻儿子的值*爸爸的乘法lazytag+儿子的区间长度*爸爸的加法lazytagans[ls(x)].v=ans[ls(x)].v*ans[x].mul+ans[x].add;ans[rs(x)].v=ans[rs(x)].v*ans[x].mul+ans[x].add;ans[ls(x)].mul*=ans[x].mul;ans[rs(x)].mul*=ans[x].mul;ans[ls(x)].add=ans[x].add+ans[ls(x)].add*ans[x].mul;ans[rs(x)].add=ans[x].add+ans[rs(x)].add*ans[x].mul;ans[x].mul=1;ans[x].add=0;
}
void updata(int l,int r,int nl,int nr,int x,int k)
{//if(nl<nr)pushdown(x,nl,nr);int mid=(nl+nr)/2;if(nl>=l&&nr<=r){ans[x].v=(ans[x].v+k);//ans[x].mul=(ans[x].mul);ans[x].add=(ans[x].add+k);return ;}pushdown(x,nl,nr);if(mid>=l){updata(l,r,nl,mid,ls(x),k);}if(mid<r){updata(l,r,mid+1,nr,rs(x),k);}pushup(x);}
int query(int l,int r,int nl,int nr,int x)
{int res=inf;int mid=(nl+nr)/2;if(nl>=l&&nr<=r){return ans[x].v;//ans[x].mul=(ans[x].mul)%p;//ans[x].add=(ans[x].add+k)%p;//return ;}pushdown(x,nl,nr);if(mid>=l){res=min(res,query(l,r,nl,mid,ls(x)));}if(mid<r){res=min(res,query(l,r,mid+1,nr,rs(x)));}pushup(x);return res;}void upd(ll x1,ll y1,ll x2,ll y2)
{ll xl=0,xr=0,yl=0,yr=0;if(x2-x1>=d)xr=d,xl=1;else xl=((x1%d+d))%d+1,xr=(((x2-1)%d+d))%d+1;if(y2-y1>=d)yr=d,yl=1;else yl=((y1%d+d))%d+1,yr=(((y2-1)%d+d))%d+1;if(xl<=xr)if(yl<=yr){add[yl].push_back({xl,xr});del[yr+1].push_back({xl,xr});}else {add[1].push_back({xl,xr});del[yr+1].push_back({xl,xr});add[yl].push_back({xl,xr});del[d+1].push_back({xl,xr});}else if(yl<=yr){add[yl].push_back({1,xr});del[yr+1].push_back({1,xr});add[yl].push_back({xl,d});del[yr+1].push_back({xl,d});}else {add[1].push_back({1,xr});del[yr+1].push_back({1,xr});add[yl].push_back({1,xr});del[d+1].push_back({1,xr});add[1].push_back({xl,d});del[yr+1].push_back({xl,d});add[yl].push_back({xl,d});del[d+1].push_back({xl,d});}
}
int main()
{cin>>n>>d;for(int i=1;i<=n;i++){int x1=0,y1=0,x2=0,y2=0;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);upd(x1,y1,x2,y2);}//ll t,x,y,k;bt(1,1,d);//cout<<query(1,n,1,n,1)<<endl;for(int i=1;i<=d;i++){//auto [l,r]:add[y]for(int j=0;j<add[i].size();j++){updata(add[i][j].first,add[i][j].second,1,d,1,1);}for(int j=0;j<del[i].size();j++){updata(del[i][j].first,del[i][j].second,1,d,1,-1);}if(query(1,d,1,d,1)==0)for(int x=1;x<=d;x++){if(query(x,x,1,d,1)==0)//带入d 别带入n{ //有的人因为带入的是n卡了1.5hcout<<"YES"<<endl<<x-1<<" "<<i-1<<endl;return 0;}}}printf("NO\n");return 0;
}