求n個矩形面積——坐标離散化

最開始接觸離散的時候是在實驗室第一次暑期集訓的時候，好像是wuyuqi大佬講的，但是當時根本就沒聽懂這是個什麼東西，感覺聽名字這麼高大上，有點難了解。是以當時就沒花時間去研究。

這兩天在補題的時候遇到了這個問題，就看了一些大佬的解釋，算是有一丢丢了解了

坐标離散我個人的了解就是把一個坐标平面上的有用的點儲存，沒有關系的點壓縮（因為沒有用的點對實際結果根本沒有任何影響）

就以voj的1056題來做一個示範：

         這題按照最平常的想法就是把矩形内的标記，然後整個圖搜尋，就可以得出共覆寫了多少範圍。但是範圍是-10^8~10^8，這麼搜顯然不可能。是以要怎麼樣呢？

就是把有用的點儲存，無關的點壓縮。什麼是有用的點儲存，什麼是無關的點壓縮？給出的坐标就是有用的點，-10^8~10^8内的範圍内除了給出的坐标範圍其他全是沒用的點，都要壓縮。

有用的值其實隻有這麼幾個。這些值将作為新的坐标值重新劃分整個平面，省去中間的若幹坐标值沒有影響。我們可以将坐标範圍“離散化”到1到200 

之間的數，于是一個200*200的二維數組就足夠了。

現在用個小例子來模拟一下：

注意左邊的10* 7的數組是如何等價地轉化為右邊兩個4*4的數組的 

再就是代碼實作了：

如上資料示例   x[ ]={ 1, 3, 7, 10 };

                           y[ ]={ 1,  2,  5,  7 };

按代碼枚舉的順序是如上圖，先看(1,1)點， if(x[i]>=x1[k]&&y[j]>=y1[k]&&x[i+1]<=x2[k]&&y[j+1]<=y2[k])判斷是否是矩形内的然後按順序枚舉，發現（1,1）點不是，再看（1,2）點，s=s(x+1,y+1)-s(x,y)即框2，符合在矩形内，ans+=s,枚舉完了，就得出結果了

include<cstdio>
include<cstdlib>
include<algorithm>
include<iostream>
define MAXn 100
using namespace std;
int n;
long long x1[MAXn+1],y1[MAXn+1];
long long x2[MAXn+1],y2[MAXn+1];
long long x[2MAXn+1],y[2MAXn+1];
long long S,ans;
int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;i++) 
    { 
        scanf("%I64d%I64d%I64d%I64d",&x1[i],&y1[i],&x2[i],&y2[i]); 
        x[2i-1]=x1[i]; 
        x[2i]=x2[i]; 
        y[2i-1]=y1[i];
        y[2i]=y2[i]; 
    } 
    sort(x+1,x+2n+1); 
    sort(y+1,y+2n+1); 
    for(int i=1;i<=2n-1;i++) //枚舉每一個機關橫坐标，這兩句看圖 
        for(int j=1;j<=2n-1;j++)  //枚舉每一個機關縱坐标
        { 
            S=(x[i+1]-x[i])*(y[j+1]-y[j]);
            for(int k=1;k<=n;k++) //枚舉每一個矩形塊 
                if(x[i]>=x1[k]&&y[j]>=y1[k]&&x[i+1]<=x2[k]&&y[j+1]<=y2[k])//這句是離散化
                { ans+=S; break; }//注意這個break,用的妙
        } 
    printf("%I64d",ans); return 0; 
}