算法复习之坐标离散化

#include
#include
using namespace std;
const int maxn=210;
int x1[maxn],y1[maxn],x2[maxn],y2[maxn],x[maxn],y[maxn];
void init() {
    for(int i=0; i) {
        x1[i]=y1[i]=x2[i]=y2[i]=x[i]=y[i]=0;
    }
}
int main() {
    int n;
    while(cin>>n) {
        init();
        for(int i=1; i) {
            cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
            x[2*i-1]=x1[i];
            x[2*i]=x2[i];
            y[2*i-1]=y1[i];
            y[2*i]=y2[i];
        }
        sort(x+1,x+2*n+1);
        sort(y+1,y+2*n+1);
        int sum=0;
        //枚举每一个单位，，判断是否符合条件
        for(int i=1; i2*n-1; i++)
            for(int j=1; j2*n-1; j++) {
                int s=((x[i+1]-x[i])*(y[i+1]-y[i]));
                for(int k=1; k) {
                    if(x[i]>=x1[k]&&y[i]>=y1[k]&&x[i+1]1]y2[k]) {
                        sum+=s;
                        break;
                    }
                }
            }
        coutendl;
    }
    return 0;
}

//离散化函数，对坐标x1,x2进行离散化，并返回离散化之后的宽度
//其中x1,x2代表一条直线开头与结尾的列 y为行 
//重新形成一个数组
#include
#include
#include
#includeint Compress(int *x1,int *x2,int w) {
    vectorint> s;//只需存前后及自身坐标
    for(int i=0; i) {
        for(int d=-1; d1; d++) {
            //首先判断前后
            int tx1=x1[i]+d;
            int tx2=x2[i]+d;
            if(1w)  s.push_back(tx1);
            if(1w)  s.push_back(tx2);
            //进行排序删除重复的
        }
    }
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    //重新分配顺序
    for(int i=0; i) {
        x1[i]=find(s.begin(),s.end(),x1[i])-s.begin();
        x2[i]=find(s.begin(),s.end(),x2[i])-s.begin();
    }
   return s.size();
}