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;  
}