洛谷 / 题目列表 / 题目详情
P1884 [USACO12FEB]Overplanting S
提交
1.82k
通过
528
时间限制
1.00s
内存限制
125.00MB
提交答案
加入收藏
题目提供者
FarmerJohn2
难度
普及+/提高
历史分数
0
提交记录 查看题解
标签
USACO
2012
进入讨论版
相关讨论
推荐题目
展开
题目描述
Farmer John has purchased a new machine that is capable of planting grass within any rectangular region of his farm that is “axially aligned” (i.e., with vertical and horizontal sides). Unfortunately, the machine malfunctions one day and plants grass in not one, but N (1 <= N <= 1000) different rectangular regions, some of which may even overlap.
Given the rectangular regions planted with grass, please help FJ compute the total area in his farm that is now covered with grass.
在一个笛卡尔平面坐标系里（则X轴向右是正方向，Y轴向上是正方向），有N(1<=N<=10001<=N<=1000)个矩形，第i个矩形的左上角坐标是(x1, y1),右下角坐标是（x2,y2）。问这N个矩形所覆盖的面积是多少？注意：被重复覆盖的区域的面积只算一次。
输入格式
第一行，一个整数Ｎ。 (1<=N<=10001<=N<=1000)。
接下来有N行，每行描述一个矩形的信息，分别是矩形的x1、y1、x2、y2。
其中 -108<=x1,y1,x2,y2<=108−10
8
<=x1,y1,x2,y2<=10
8
。
输出格式
一个整数，被N个矩形覆盖的区域的面积。
输入输出样例
输入 #1复制
2
0 5 4 1
2 4 6 2
输出 #1复制
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
#include <stack>
#include <map>
#include <cmath>
#include <set>
#include <cstdlib>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
const int maxn=1e6+5;
ll x[maxn<<1],cnt,maxx,val[maxn<<1];
#define ls (rt<<1)
#define rs (rt<<1|1)
struct node{
ll x,ay,by,k;
bool operator<(const node &a)const{
return x<a.x;
}
}e[maxn<<2];
struct node1{
ll l,r,cnt,len;
}t[maxn<<2];
void pushup(ll rt){
if(t[rt].cnt)t[rt].len=x[t[rt].r+1]-x[t[rt].l];
else t[rt].len=t[ls].len+t[rs].len;
}
void build(ll rt,ll l,ll r){
t[rt].l=l;
t[rt].r=r;
if(l==r)return ;
ll mid=(t[rt].l+t[rt].r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
void add(ll rt,ll l, ll r,ll v){
if(l<=t[rt].l&&t[rt].r<=r){
t[rt].cnt+=v;
pushup(rt);
return ;
}
int mid=t[rt].l+t[rt].r>>1;
if(l<=mid)add(ls,l,r,v);
if(mid<r)add(rs,l,r,v);
pushup(rt);
}
int main(){
ll n;
read(n);
ll x1,x2,y1,y2;
rep(i,1,n){
read(x1),read(y1);
read(x2),read(y2);
e[(i<<1)-1]=node{x1,y1,y2,1};
e[i<<1]=node{x2,y1,y2,-1};
x[++cnt]=y1;
x[++cnt]=y2;
}
sort(x+1,x+cnt+1);
cnt=unique(x+1,x+(n<<1)+1)-x-1;
rep(i,1,2*n){
ll pos1=lower_bound(x+1,x+cnt+1,e[i].ay)-x;
ll pos2=lower_bound(x+1,x+cnt+1,e[i].by)-x;
e[i].ay=pos1;
e[i].by=pos2;
}
sort(e+1,e+2*n+1);
build(1,1,cnt);
ll ans=0;
rep(i,1,(n<<1)){
add(1,e[i].ay,e[i].by-1,e[i].k);
ans+=t[1].len*(e[i+1].x-e[i].x);
}
write(ans);
}