题意:求矩形面积并
分析:本来是要学习扫描线的,不过还没看懂。。囧。。在看了黑书之后,发现这题数据规模如此小(100个矩形),于是YY出了一种方法:
1.首先把X,Y坐标都进行离散化。
2.离散化之后,将整个平面划分成很多面积不等的小矩形。
3.枚举每个大矩形,得到大矩形离散化后的左上角点和右下角点的位置。
4.把每个小矩形标记为c[i][j]表示第i行第j列个矩形是否已经被计算过,那么在大矩形中枚举其包含的所有小矩形,如果小矩形未被包含着总面积增加小矩形的面积,并标记该小矩形。
各种蛋疼:1.自己2B的把左移写成右移,结果数组开小了,检查了半天。。。
2.POJ上面G++不能使用%lf,换成C++后就过了。
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 222;
struct Rec{
double x1,y1,x2,y2;
}R[MAXN];
double X[MAXN<<2],Y[MAXN<<2],ans;
bool c[MAXN<<2][MAXN<<2];
int sx,sy,n;
void init(){
memset(c,0,sizeof(c));
ans = 0;
}
void disc(){
int tpx=0,tpy=0;sx=1,sy=1;
for(int i=0;i<n;i++){
X[tpx++] = R[i].x1;
X[tpx++] = R[i].x2;
Y[tpy++] = R[i].y1;
Y[tpy++] = R[i].y2;
}
sort(X,X+tpx);sort(Y,Y+tpy);
for(int i=1;i<tpx;i++)if(X[i]!=X[i-1])X[sx++] = X[i];
for(int i=1;i<tpy;i++)if(Y[i]!=Y[i-1])Y[sy++] = Y[i];
}
int search(double k,int l,int r,double arr[]){
int m;
while(l<=r){
m = (l+r)>>1;
if(arr[m]==k)return m;
else if(k<arr[m])r = m-1;
else l = m+1;
}
return -1;
}
double area(int x,int y){
return (X[x]-X[x-1])*(Y[y]-Y[y-1]);
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int cas = 0;
while(scanf("%d",&n)!=EOF&&n>0){
cas++;
for(int i=0;i<n;i++)scanf("%lf%lf%lf%lf",&R[i].x1,&R[i].y1,&R[i].x2,&R[i].y2);
init();
disc();
for(int i=0;i<n;i++){
int px1,px2,py1,py2;
px1 = search(R[i].x1,0,sx-1,X);
px2 = search(R[i].x2,0,sx-1,X);
py1 = search(R[i].y1,0,sy-1,Y);
py2 = search(R[i].y2,0,sy-1,Y);
px1++,py1++;
for(int j=py1;j<=py2;j++){
for(int k=px1;k<=px2;k++){
if(!c[j][k]){
c[j][k]=1;
ans+=area(k,j);
}
}
}
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas,ans);
}
return 0;
}
分享到:
相关推荐
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
2遍dp poj_3613解题报告 poj_3613解题报告
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
POJ 3131 双向BFS解立体八数码问题
O(nlogn)凸包问题 poj2187
poj两道题的c++实现。已经测试过可以通过oj
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
poj 3310 的代码和方法说明,个人原创
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。
POJ上面题目的解题报告。涵盖挺多的。可作参考。代码都正确。ACM新手入门必下~~ 加油...