這就是usaco 前面的windows area的變形。

/*
ID：jinbo wu
TASK:rect1
LANG:C++
*/ 
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int max(int a,int b)
{return a>b?a:b;
}
const int maxn=3000;
int x0[maxn],x[maxn],y0[maxn],y[maxn];
int ans[maxn],color[maxn];
int n;
void solve(int i,int tx0,int ty0,int tx,int ty,int c)
{if(tx0>=tx||ty0>=ty)return ;if(i>n){ans[c]+=(tx-tx0)*(ty-ty0);return ;}solve(i+1,tx0,ty0,min(x0[i],tx),ty,c);solve(i+1,max(tx0,x[i]),ty0,tx,ty,c);solve(i+1,max(x0[i],tx0),max(ty0,y[i]),min(tx,x[i]),ty,c);solve(i+1,max(tx0,x0[i]),ty0,min(tx,x[i]),min(ty,y0[i]),c);
}
int main()
{freopen("rect1.in","r",stdin);freopen("rect1.out","w",stdout);//int n;cin>>x[0]>>y[0]>>n;color[0]=1;for(int i=1;i<=n;i++){cin>>x0[i]>>y0[i]>>x[i]>>y[i]>>color[i];}ans[color[n]]=(x[n]-x0[n])*(y[n]-y0[n]);for(int i=n-1;i>=0;i--){solve(i+1,x0[i],y0[i],x[i],y[i],color[i]);}for(int i=1;i<=2500;i++)if(ans[i]){cout<<i<<' '<<ans[i]<<endl;}
}

總結(jié)

以上是生活随笔為你收集整理的usaco Shaping Regions的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。