usaco卡了很久的一个题，因为这个题三个月没有碰usaco。开始是用了直接模拟的方法，其实是可以过掉除了最后一个数据外的所有数据的。最后一个数据就是1w*1w的，内存限制。usaco自己给的提示我硬是没看懂。
利用了矩形分割的方法。每次加入一个新矩形都把它和原来的矩形比较，如果没有交集就不处理，直接处理下一个矩形，否则分四种情况：
(1) 原来的矩形上部超出了现有矩形，把超出的部分分割为一个新矩形。加入矩形库中。
(2) 原来的矩形下部超出……
(3) 左部……
(4) 右部……
根据以上四种情况分别处理，再把原来的那个矩形从矩形库中删除。我写的比较挫的代码，还好一遍过了。
/*
ID: like_091
PROG: rect1
LANG: C++
*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <fstream>
#include <cstdio>
using namespace std;
struct area{
int lx, ly, rx, ry, v;
};
vector<area> a;
bool deal(area temp, int i){
//没有交集就不用处理
if (temp.lx >= a[i].rx || temp.rx <= a[i].lx)return false;
if (temp.ly >= a[i].ry || temp.ry <= a[i].ly)return false;
area b;
//上面还有未被覆盖的地方
if (a[i].ry > temp.ry){
b.lx = a[i].lx;
b.ly = temp.ry;
b.rx = a[i].rx;
b.ry = a[i].ry;
b.v = a[i].v;
a.push_back(b);
}
//下面还有未被覆盖的地方
if (a[i].ly < temp.ly){
b.lx = a[i].lx;
b.ly = a[i].ly;
b.rx = a[i].rx;
b.ry = temp.ly;
b.v = a[i].v;
a.push_back(b);
}
//左边还有未被覆盖的地方
if (a[i].lx < temp.lx){
b.lx = a[i].lx;
b.rx = temp.lx;
b.ly = max(a[i].ly, temp.ly);
b.ry = min(a[i].ry, temp.ry);
b.v = a[i].v;
a.push_back(b);
}
//右边还有未被覆盖的地方
if (a[i].rx > temp.rx){
b.lx = temp.rx;
b.rx = a[i].rx;
b.ly = max(a[i].ly, temp.ly);
b.ry = min(a[i].ry, temp.ry);
b.v = a[i].v;
a.push_back(b);
}
return true;
}
int main(){
int row, col, n, sum[3000];
ifstream cin("rect1.in");
ofstream cout("rect1.out");
while (cin>>row>>col>>n){
a.clear();
area d;
d.lx = d.ly = 0;
d.v = 1;
d.rx = row;
d.ry = col;
a.push_back(d);
area temp;
for (int i = 0; i < n; i++){
cin>>temp.lx>>temp.ly>>temp.rx>>temp.ry>>temp.v;
for (int j = a.size() - 1; j >= 0; j--){
if (deal(temp, j)){
//如果有交集，原来的矩形被分割，不必再保存
a.erase(a.begin() + j);
}
}
a.push_back(temp);
}
memset(sum, 0, sizeof(sum));
for (int i = 0; i < a.size(); i++)
sum[a[i].v] += (a[i].rx - a[i].lx) * (a[i].ry - a[i].ly);
for (int i = 0; i < 3000; i++)
if (sum[i] > 0)
cout<<i<<" "<<sum[i]<<endl;
}
return 0;
}
原文链接: https://www.cnblogs.com/neulike/archive/2011/08/02/2124828.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/29808
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
