首页 > 代码库 > HDU1255 覆盖的面积 【扫描线】
HDU1255 覆盖的面积 【扫描线】
覆盖的面积
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3743 Accepted Submission(s): 1838
Problem Description
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
Input
输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.
注意:本题的输入数据较多,推荐使用scanf读入数据.
注意:本题的输入数据较多,推荐使用scanf读入数据.
Output
对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.
Sample Input
2 5 1 1 4 2 1 3 3 7 2 1.5 5 4.5 3.5 1.25 7.5 4 6 3 10 7 3 0 0 1 1 1 0 2 1 2 0 3 1
Sample Output
7.63 0.00
题意:给定一些矩形的左下角与右上角的坐标,求这些矩形间的重叠次数在2次及以上的地方的面积和。
题解:这题跟POJ1151很像,主要区别在pushUp函数上,每段区间分为一次覆盖和多次覆盖,因此需要分别统计它们的长度,这样才容易求最终面积。
#include <stdio.h> #include <string.h> #include <algorithm> #define maxn 2002 #define lson l, mid, rt << 1 #define rson mid, r, rt << 1 | 1 using namespace std; struct Node { double y1, y2, onceLen, moreLen; int covers; } T[maxn << 2]; struct Node2 { double x, y1, y2; int isLeft; } xNode[maxn]; double yNode[maxn]; bool cmp(Node2 a, Node2 b) { return a.x < b.x; } void pushUp(int l, int r, int rt) { if(T[rt].covers > 1) { T[rt].moreLen = T[rt].y2 - T[rt].y1; T[rt].onceLen = 0.0; } else if(T[rt].covers == 1) { if(r - l == 1) { T[rt].moreLen = 0.0; T[rt].onceLen = T[rt].y2 - T[rt].y1; return; } T[rt].moreLen = T[rt << 1].onceLen + T[rt << 1 | 1].onceLen + T[rt << 1].moreLen + T[rt << 1 | 1].moreLen; T[rt].onceLen = T[rt].y2 - T[rt].y1 - T[rt].moreLen; } else { if(r - l == 1) { T[rt].onceLen = T[rt].moreLen = 0.0; return; } T[rt].onceLen = T[rt << 1].onceLen + T[rt << 1 | 1].onceLen; T[rt].moreLen = T[rt << 1].moreLen + T[rt << 1 | 1].moreLen; } } void build(int l, int r, int rt) { T[rt].onceLen = T[rt].moreLen = 0.0; T[rt].covers = 0; T[rt].y1 = yNode[l]; T[rt].y2 = yNode[r]; if(r - l == 1) return; int mid = (l + r) >> 1; build(lson); build(rson); } void update(Node2 x, int l, int r, int rt) { if(x.y1 == T[rt].y1 && x.y2 == T[rt].y2) { T[rt].covers += x.isLeft; pushUp(l, r, rt); return; } int mid = (l + r) >> 1; if(x.y2 <= yNode[mid]) update(x, lson); else if(x.y1 >= yNode[mid]) update(x, rson); else { Node2 x1 = x, x2 = x; x1.y2 = x2.y1 = yNode[mid]; update(x1, lson); update(x2, rson); } pushUp(l, r, rt); } int main() { //freopen("stdin.txt", "r", stdin); int n, i, id, t; double x1, y1, x2, y2, sum; scanf("%d", &t); while(t--) { scanf("%d", &n); for(i = id = 0; i < n; ++i) { scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); yNode[id] = y1; xNode[id].x = x1; xNode[id].y1 = y1; xNode[id].y2 = y2; xNode[id++].isLeft = 1; yNode[id] = y2; xNode[id].x = x2; xNode[id].y1 = y1; xNode[id].y2 = y2; xNode[id++].isLeft = -1; } sort(yNode, yNode + id); build(0, id - 1, 1); sort(xNode, xNode + id, cmp); for(i = 0, sum = 0.0; i < id - 1; ++i) { update(xNode[i], 0, id - 1, 1); sum += T[1].moreLen * (xNode[i + 1].x - xNode[i].x); } printf("%.2lf\n", sum); } return 0; }
HDU1255 覆盖的面积 【扫描线】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。