将每个矩形拆分为2条横边和2条纵边，用一个结构体记录，
以横边为例，记录开始的横坐标s，结束的横坐标e，该横边的纵坐标p，若该横边是一个矩形下边的边，则start为ture，若是一个矩形上边的边，则为false，
记录后按纵坐标从小到大排序，若纵坐标相等的，start为ture的优先。
(PS：STL的sort中，对于比较函数，若两个元素相等，则必需返回false，否则会导致sort死循环）
排序后，从小到大进行扫描。
使用level作为记录数组，
对于start = true 的横边，对于j = [s, e) ，进行level[j] ++ 若level[j]==1， ans++；
对于start = false的横边，对于j = [s, e)，进行level[j] -- 若level[j]==0， ans++；
（画个简图领会下）
纵边如此类推。
/**//*
ID: lorelei3
TASK: picture
LANG: C++
*/
#include <fstream>
#include <algorithm>
#include <memory.h>
using namespace std;
const int MAX = 20005;
struct Line
{
int s,e,p;
bool start;
bool operator < ( const Line &l) const{
if(p==l.p){
if(l.start == start)
return false;
if(start)
return 1;
else
return 0;
}
return p<l.p?1:0;
}
};
ifstream fin("picture.in");
ofstream fout("picture.out");
Line lx[MAX], ly[MAX];
long ans;
int n,m;
void input(){
fin>>n;
int x1,x2,y1,y2,lenx=0,leny=0;
m=n+n;
for(int i=0; i<=n; ++i){
fin>>x1>>y1>>x2>>y2;
lx[lenx].s=x1, lx[lenx].e=x2, lx[lenx].p=y1;
lx[lenx].start=true;
lenx++;
lx[lenx].s=x1, lx[lenx].e=x2, lx[lenx].p=y2;
lx[lenx].start=false;
lenx++;
ly[leny].s=y1, ly[leny].e=y2, ly[leny].p=x1;
ly[leny].start=true;
leny++;
ly[leny].s=y1, ly[leny].e=y2, ly[leny].p=x2;
ly[leny].start=false;
leny++;
}
qsort(lx, m, sizeof(Line), cmp);
qsort(ly, m, sizeof(Line), cmp);
sort(lx, lx+m);
sort(ly, ly+m);
}
int level[20005], zero=10000;
void solve(Line *l){
memset(level, 0, sizeof(level));
for(int i=0; i<m; ++i){
if(l[i].start){
for(int k=zero+l[i].s; k<(zero+l[i].e); ++k){
level[k]++;
if(level[k]==1)
ans++;
}
}else{
for(int k=zero+l[i].s; k<(zero+l[i].e); ++k){
level[k]--;
if(level[k]==0)
ans++;
}
}
}
}
void output(){
fout<<ans<<endl;
}
int main(){
input();
solve(lx);
solve(ly);
output();
return 0;
}
posted on 2011-02-17 13:56
小阮 阅读(418)
评论(0) 编辑 收藏 引用 所属分类:
USACO