首页 > 代码库 > 2149 矩形周长
2149 矩形周长
2149 矩形周长
USACO
时间限制: 1 s
空间限制: 16000 KB
题目等级 : 大师 Master
题目描述 Description
N(N<5000) 张矩形的海报，照片和其他同样形状的图片贴在墙上。它们的边都是垂直的或水平的。每个矩形可以部分或者全部覆盖其他矩形。所有的矩形组成的集合的轮廓称为周长。写一个程序计算周长。
图 1 是一个有 7 个矩形的例子：
图 1.一个 7 个矩形的集合
对应的轮廓为图 2 所示的所有线段的集合：
图 2. 矩形集合的轮廓
所有矩形的顶点坐标均为整数。所有的坐标都在 [-10000，10000] 的范围内，并且任何一个矩形面积都为整数。结果的值可能需要 32 位有符号整数表示。
输入描述 Input Description
第1行: N，张贴在墙上的矩形的数目。
第 2..N+1行 接下来的N行中，每行都有两个点的坐标，分别是矩形的左下角坐标和右上角坐标。每一个坐标由 X 坐标和 Y 坐标组成。
输出描述 Output Description
只有一行，为一个非负整数，表示输入数据中所有矩形集合的轮廓长度。
样例输入 Sample Input
7-15 0 5 10-5 8 20 2515 -4 24 140 -6 16 42 15 10 2230 10 36 2034 0 40 16
样例输出 Sample Output
228
数据范围及提示 Data Size & Hint
范围如题所述
分类标签 Tags 点此展开
USACO
/*不写点什么总是不好的，但我又懒，转载zjk‘s文字解析： 这道题暴力竟然可以过，可能是数据比较弱，就是把矩形拆成两条横边和纵边，然后暴力给一条边上的每一个点加权值， 如果用线段树的话，可能是用线段树维护区间和吧，貌似很麻烦的样子。 但是这个题有很多细节需要注意（扫描线的题大都有很多细节）。 为了使包含关系的边只出现一次，再加入左边时，要在区间权值为空（即以前未出现过包含这条边的边）时才更新答案， 另外在排序时如果位置相同，把左边排在前面，这是为了解决两个矩形前后重合的情况。 */#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=1e4+10;struct node{ int l,r,h,id; bool operator < (const node &a)const{ return h==a.h?id<a.id:h<a.h; }}A[N*2],B[N*2];int n,m,cnt,f[N*4];int main(){ scanf("%d",&n); for(int i=1,x1,y1,x2,y2;i<=n;i++){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1+=10000,y1+=10000,x2+=10000,y2+=10000; ++cnt; A[cnt].l=x1;A[cnt].r=x2;A[cnt].h=y1;A[cnt].id=0; B[cnt].l=y1;B[cnt].r=y2;B[cnt].h=x1;B[cnt].id=0; ++cnt; A[cnt].l=x1;A[cnt].r=x2;A[cnt].h=y2;A[cnt].id=1; B[cnt].l=y1;B[cnt].r=y2;B[cnt].h=x2;B[cnt].id=1; } sort(A+1,A+cnt+1);sort(B+1,B+cnt+1); int ans=0; for(int i=1;i<=cnt;i++){ for(int j=A[i].l;j<A[i].r;j++){ if(!A[i].id){if(!f[j]) ans++;f[j]++;} else {f[j]--;if(!f[j]) ans++;} } } memset(f,0,sizeof f); for(int i=1;i<=cnt;i++){ for(int j=B[i].l;j<B[i].r;j++){ if(!B[i].id){if(!f[j]) ans++;f[j]++;} else {f[j]--;if(!f[j]) ans++;} } } printf("%d",ans); return 0;}
2149 矩形周长
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。