大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
题目大意:
n个矩形,将一个大矩形分成 n+1 块。矩形之间不重合,可是包括。求这n+1个矩形的面积
思路分析:
用线段树记录他们之间的父子关系。然后dfs 计算面积。
当给出的矩形上边的时候,就要记录到该矩形的父亲去。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define maxn 70010 using namespace std; typedef long long LL; int cov[maxn<<2]; LL area[maxn<<1]; int W,H; struct node { int s,e,h,type; bool operator < (const node &cmp)const { return h<cmp.h; } }scline[maxn<<1]; struct foo { int s,e,h; }sqr[maxn<<2]; int x[maxn<<1]; int pre[maxn<<1]; void pushdown(int num) { if(cov[num]!=-1){ cov[num<<1]=cov[num<<1|1]=cov[num]; cov[num]=-1; } } void build(int num,int s,int e) { cov[num]=0; if(s==e)return; int mid=(s+e)>>1; build(lson); build(rson); } void update(int num,int s,int e,int l,int r,int val) { if(l<=s && r>=e) { if(val<0)cov[num]=pre[abs(val)]; else cov[num]=val; return; } pushdown(num); int mid=(s+e)>>1; if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); } int PRE; int query(int num,int s,int e,int l,int r) { if(cov[num]!=-1) { return cov[num]; } pushdown(num); int mid=(s+e)>>1; if(r<=mid)return query(lson,l,r); else if(l>mid)return query(rson,l,r); else return query(lson,l,mid); } int head[maxn<<1]; int next[maxn<<1]; int to[maxn<<1]; int tot; void add(int a,int b) { next[tot]=head[a]; head[a]=tot; to[tot]=b; tot++; } LL getarea(int index) { return (LL)sqr[index].h*(LL)(sqr[index].e-sqr[index].s); } void dfs(int x) { for(int s=head[x];s!=0;s=next[s]) { area[x]-=getarea(to[s]); dfs(to[s]); } } int main() { int n; while(scanf("%d",&n)!=EOF) { tot=1; memset(pre,0,sizeof pre); scanf("%d%d",&W,&H); area[0]=(LL)W*(LL)H; sqr[0].s=0;sqr[0].e=W;sqr[0].h=H; for(int i=1;i<=n;i++) { int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); sqr[i].s=x1;sqr[i].e=x2;sqr[i].h=y2-y1; scline[2*i-1].s=x1; scline[2*i-1].e=x2; scline[2*i-1].h=y1; scline[2*i-1].type=i; x[2*i-1]=x1; scline[2*i].s=x1; scline[2*i].e=x2; scline[2*i].h=y2; scline[2*i].type=-i; x[2*i]=x2; } x[2*n+1]=0; x[2*n+2]=W; for(int i=1;i<=n;i++) area[i]=getarea(i); sort(x+1,x+2*n+3); int m=unique(x+1,x+2*n+3)-(x+1)-1; build(1,0,m); sort(scline+1,scline+2*n+1); memset(head,0,sizeof head); tot=1; for(int i=1;i<=2*n;i++) { int l=lower_bound(x+1,x+m+1,scline[i].s)-(x+1); int r=lower_bound(x+1,x+m+1,scline[i].e)-(x+1); if(scline[i].type>0) { pre[scline[i].type]=query(1,0,m,l,r); printf("%d %d\n",scline[i].type,pre[scline[i].type]); add(pre[scline[i].type],scline[i].type); } update(1,0,m,l,r,scline[i].type); } dfs(0); sort(area,area+n+1); for(int i=0;i<=n;i++) printf("%lld%c",area[i],i==n?'\n':' '); } return 0; } /* 2 5 5 1 1 4 4 2 2 3 3 4 10 10 1 1 5 5 2 2 3 4 6 1 9 9 7 2 8 3 4 10 10 1 1 9 6 2 2 5 5 2 7 8 9 3 6 5 7 */
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118539.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...