USACO Section 3.1 Shaping Regions - 矩陣切割..

   開始聽對裡的大大說這是二維線段樹..沒敢寫..後來再一想..資料範圍N<=2500..那麼N^2的算法可以過...再一想...其實就是拿到一個矩陣然後和以後填上去的矩陣來比較..去掉重合的部分..将矩陣切割成若幹小矩陣..然後這些小矩陣再繼續往後面看有沒有和後面填的矩陣重合的矩形區域(矩形和矩形重合的區域也一定是矩形)..有的做相同的操作...後來才知道這就是矩陣切割..時間複雜度是N^2..可以接受..用遞歸來實作很友善..遞歸時我就假想目前矩陣的重複區域矩形是在目前這個矩形内部的..那麼為了切掉這個重複的中間部分..那麼我要把這個矩形切成四塊.如圖:

     就讓他這麼切..為了防止一些切出來不滿足要求或者切出來面積為0沒有意義的區域..那麼就在遞歸的時候加個判斷.看目前的矩形是否是合法的..也就是lx<ux && ly<ux

/*  
ID: zzyzzy12  
LANG: C++  
TASK: rect1
*/    
#include<iostream>    
#include<istream>
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<stack>
#include<algorithm>    
#include<queue> 
#define oo 2000000000
#define ll long long
using namespace std;  
struct node
{
      int lx,ly,ux,uy,color;      
}s[5510],a[50001];
int ans[2510],A,B,N,i,num;  
void cut(node h,int m)
{
      int i,lx,ly,ux,uy;
      node k; 
      if (h.lx>=h.ux || h.ly>=h.uy) return;
      for (i=m+1;i<=N;i++) 
        if (!(s[i].lx>=h.ux || s[i].ux<=h.lx || s[i].ly>=h.uy || s[i].uy<=h.ly))  
           break;
      if (i>N)
      {
              a[++num]=h;
              return;
      } 
      if (h.lx>=s[i].lx && h.ux<=s[i].ux && h.ly>=s[i].ly && h.uy<=s[i].uy)  return;
      lx=max(s[i].lx,h.lx); ly=max(s[i].ly,h.ly); ux=min(s[i].ux,h.ux); uy=min(s[i].uy,h.uy);
      //-----------------
      k=h;  k.lx=ux;   cut(k,i);
      k=h;  k.ux=lx;   cut(k,i);
      k=h;  k.ly=uy; k.lx=lx; k.ux=ux;  cut(k,i);
      k=h;  k.uy=ly; k.lx=lx; k.ux=ux;  cut(k,i);        
      //-----------------   
      return;
}
int main()
{
      freopen("rect1.in","r",stdin);  
      freopen("rect1.out","w",stdout);  
      memset(ans,0,sizeof(ans));
      scanf("%d%d%d",&A,&B,&N);
      for (i=1;i<=N;i++)  scanf("%d%d%d%d%d",&s[i].lx,&s[i].ly,&s[i].ux,&s[i].uy,&s[i].color); 
      s[0].lx=s[0].ly=0; s[0].ux=A; s[0].uy=B; s[0].color=1; 
      num=0;
      for (i=N;i>=0;i--)  
          cut(s[i],i); 
      for (i=1;i<=num;i++) ans[a[i].color]+=(a[i].ux-a[i].lx)*(a[i].uy-a[i].ly);
      for (i=1;i<=2500;i++)
      if (ans[i]) printf("%d %d\n",i,ans[i]);  
      return 0;   
}