hdu 1542(数学+yy)
题意:
给你n个矩形的顶点坐标,求着n个矩形的面积和
将矩形分为一块一块的,重点是要标记矩形内部的整点,最后求面积=sum(对应区域的面积*对应区域的标记值)
#include"stdio.h" #include"string.h" #include"algorithm" using namespace std; #define N 101 int n; struct node { double x1,x2; double y1,y2; }A[N]; int search(double *a,double x) { int low,high,mid; low=0; high=2*n-1; while(low<=high) { mid=(low+high)/2; if(a[mid]==x)return mid; else if(a[mid]<x)low=mid+1; else high=mid-1; } return 0; } int main() { int t; int i,j,k; int xy[2*N][2*N]; double x[2*N],y[2*N]; t=1; while(scanf("%d",&n)!=-1&&n) { j=0; for(i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&A[i].x1,&A[i].y1,&A[i].x2,&A[i].y2); x[j]=A[i].x1; y[j]=A[i].y1; j++; x[j]=A[i].x2; y[j]=A[i].y2; j++; } sort(x,x+2*n); sort(y,y+2*n); memset(xy,0,sizeof(xy)); int f1,f2,f3,f4; for(i=0;i<n;i++) { f1=search(x,A[i].x1); f2=search(x,A[i].x2); f3=search(y,A[i].y1); f4=search(y,A[i].y2); for(j=f1;j<f2;j++) { for(k=f3;k<f4;k++) xy[j][k]=1; } } double ans; ans=0; for(i=0;i<2*n;i++) { for(j=0;j<2*n;j++) ans+=(x[i+1]-x[i])*(y[j+1]-y[j])*double(xy[i][j]); } printf("Test case #%d\n",t++); printf("Total explored area: %.2f\n",ans); printf("\n"); } return 0; }
补充:软件开发 , C++ ,