首页 > 代码库 > Vijos1056 图形面积
Vijos1056 图形面积
描述
桌面上放了N个平行于坐标轴的矩形，这N个矩形可能有互相覆盖的部分，求它们组成的图形的面积。
格式
输入格式
输入第一行为一个数N（1≤N≤100），表示矩形的数量。下面N行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为–10^8到10^8之间的整数。
输出格式
输出只有一行，一个整数，表示图形的面积。
样例1
样例输入1[复制]
31 1 4 32 -1 3 24 0 5 2
样例输出1[复制]
10
来源
某校NOIP模拟题
将所有的横线和竖线离散化排序，用它们将原矩形切分成一个个不重叠的小矩形，然后累计面积。
模拟赛的时候虽然想出了正解，但是x[]和y[]数组没有开long long，中途相乘的时候爆掉了（第二次犯错，上一次是海底高铁），只有60分
然而比赛的时候是windows评测，需要I64d，我开的是lld，如果真的开了long long，估计会爆零
……
hah……
1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #define LL long long 8 using namespace std; 9 const int mxn=320;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 struct node{17 int x1,x2,y1,y2;18 }a[mxn];19 int n;20 LL ans=0;21 LL x[mxn],y[mxn];22 bool use[mxn][mxn];23 void init(){24 for(int i=1;i<=n;i++){25 a[i].x1=read();a[i].y1=read();a[i].x2=read();a[i].y2=read();26 x[i*2-1]=a[i].x1;27 y[i*2-1]=a[i].y1;28 x[i*2]=a[i].x2;29 y[i*2]=a[i].y2;30 }31 sort(x+1,x+n*2+1);32 sort(y+1,y+n*2+1);33 return;34 }35 int main(){36 n=read();37 init();38 int i,j,k;39 int lim=n*2;40 for(i=1;i<=n;i++){41 for(j=1;j<lim;j++){//枚举横坐标 42 if(x[j]>a[i].x2)break;43 if(a[i].x1<=x[j] && x[j+1]<=a[i].x2)44 for(k=1;k<lim;k++){//枚举纵坐标 45 if(y[k]>a[i].y2)break;46 if(a[i].y1<=y[k] && y[k+1]<=a[i].y2)47 use[j][k]=1;48 }49 }50 }51 for(j=1;j<lim;j++)52 for(k=1;k<lim;k++){53 if(use[j][k]){54 ans+=(x[j+1]-x[j])*(y[k+1]-y[k]);55 }56 }57 printf("%lld\n",ans);58 return 0;59 }
Vijos1056 图形面积
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。