[离散化+蛮力]POJ_1151_Atlantis

题意：求矩形面积并

分析：本来是要学习扫描线的，不过还没看懂。。囧。。在看了黑书之后，发现这题数据规模如此小（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;
}