`

zoj3540

阅读更多

/*
其实就是把总共的 放置次数减去不能放置的那些就行了。而不能放置的 那部分是一个个矩形 !
所以问题 就转化为举行并的面积了。 
*/
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 50005; //矩形的最大个数
typedef int typev;
typedef long long ll;
struct seg{
	int l, r;
	int c;    //覆盖数
	typev m;  //覆盖长度
}segs[N<<3];
struct li{
	typev x, ly, hy; //ly为小的,hy为大的
	void set(typev x, typev ly, typev hy){
		this->x = x, this->ly = ly, this->hy = hy;
	}
	bool is_l;   //标记是否是左边的线段
}lis[N*2];
//左下角是(x1,y1),右上角是(x2,y2), x1<x2,y1<y2的矩形
struct rect{
	typev x1, x2, y1, y2;
}rs[N];
typev y[N<<1];
int n, cnt;
typev xs[N][2], ys[N][2];
int w, h, m;

bool cmp(li l1, li l2){
	return l1.x < l2.x;
}
void build(int id, int l, int r){
	segs[id].l = l, segs[id].r = r, segs[id].m = segs[id].c = 0;
	if(l < r - 1){
		int mid = (l+r)>>1;
		build(2*id+1, l, mid);
		build(2*id+2, mid, r);
	}
}
int binary(int l, int r, typev k){
	int mid;
	while(l <= r){
		mid = (l+r)>>1;
		if(y[mid] >= k) r = mid-1;
		else l = mid+1;
	}
	return r+1;
}
void renew(int id){
	if(segs[id].c > 0) segs[id].m = y[segs[id].r] - y[segs[id].l];
	else if(segs[id].l == segs[id].r - 1) segs[id].m = 0;
	else{
		segs[id].m = segs[2*id+1].m + segs[2*id+2].m;
	}
}
// 可以把insert和del合为一个函数
void modify(int id, int l, int r, int k){
	if(segs[id].l >= l && segs[id].r <= r){
		segs[id].c += k;
		renew(id);
	}else if(segs[id].l < segs[id].r - 1){
		int mid = (segs[id].l + segs[id].r)>>1;
		if(l < mid) modify(2*id+1, l, r, k);
		if(r > mid) modify(2*id+2, l, r, k);
		renew(id);
	}
}
//n个矩形的面积并
ll unionArea(rect* rs, int n){
	if(n <= 0) return 0;
	int i;
	typev x1, y1, x2, y2, py1, py2;
	ll area;
	for(i = 0; i < n; i++){
		x1 = rs[i].x1; y1 = rs[i].y1;
		x2 = rs[i].x2; y2 = rs[i].y2;
		lis[2*i].set(x1, y1, y2);
		lis[2*i].is_l = true;
		lis[2*i+1].set(x2, y1, y2);
		y[2*i] = y1;
		y[2*i+1] = y2;
		lis[2*i+1].is_l = false;
	}
	n <<= 1;
	sort(y, y + n);
	sort(lis, lis+n, cmp);
	cnt = unique(y, y + n) - y;
	build(0, 0, cnt-1);
	area = 0;
	for(i = 0; i < n-1; i++){
		py1 = binary(0, cnt-1, lis[i].ly);
		py2 = binary(0, cnt-1, lis[i].hy);
		if(lis[i].is_l) modify(0, py1, py2, 1);
		else modify(0, py1, py2, -1);
		area += ((ll)lis[i+1].x - lis[i].x) * (segs[0].m);
	}
	return area;
}

//输入一个正整数
template<typename T>
void getNum(T& ans){
	ans = 0;
	char ch;
	while(true){
		ch = getchar();
		if(ch >= '0' && ch <= '9') break;
	}
	ans = ch -'0';
	while(true){
		ch = getchar();
		if(!(ch >= '0' && ch <= '9')) break;
		ans = ans*10+ch-'0';
	}
}
bool input(){
	if(scanf("%d%d%d%d", &w, &h, &n, &m) == EOF) return false;
	int i;
	for(i = 0; i < n; i++){
		getNum(xs[i][0]);
		getNum(ys[i][0]);
		getNum(xs[i][1]);
		getNum(ys[i][1]);
	}
	return true;
}
ll cal(){
	if(w-m+1<=0) return 0;
	ll ans=(ll)h*(w-m+1);
	int i, rn;
	for(i=rn=0; i<n; i++){
		if(xs[i][0]-m >= 0){
			rs[rn].x1 = xs[i][0]-m;
		}else{
			rs[rn].x1 = 0;
		}
		if(xs[i][1] <= (w-m+1)){
			rs[rn].x2=xs[i][1];
		}else{
			rs[rn].x2=w-m+1;
		}
//		if(rs[rn].x1>=rs[rn].x2) continue;
		if(rs[rn].x1>rs[rn].x2) continue;
		rs[rn].y1=ys[i][0]-1;
		rs[rn].y2=ys[i][1];
		if(rs[rn].y1>rs[rn].y2) continue;
		rn++;
	}
	ans -= unionArea(rs, rn);
	return ans;
}
void solve(){
	ll ans=cal();
	int i;
	if(m > 1){ //这里是要给trick,m为1的时候,横向的和竖向的都是一样的 !
		swap(w, h);
		for(i=0; i<n; i++){
			swap(xs[i][0], ys[i][0]);
			swap(xs[i][1], ys[i][1]);
		}
		ans += cal();
	}
	cout<<ans<<endl;

//	printf("%I64d\n", ans);
//	printf("%lld\n", ans);
}
int main(){
	//freopen("in.txt", "r", stdin);

	while(input()) solve();
	return 0;
}
 
分享到:
评论

相关推荐

    zoj 1002_zoj1002_

    【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...

    zoj 源码700题

    【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...

    ZOJ:浙江大学程序在线评测系统.docx

    ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...

    浙江大学ZOJ题目分类

    浙江大学ZOJ题目分类旨在为编程学习者提供一个系统化的训练平台,帮助他们在算法和编程技能上实现质的飞跃。ZOJ平台提供的分类题目包括但不限于基础算法、数据结构、动态规划以及模拟问题等,这些分类覆盖了计算机...

    zoj.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar

    标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...

    ZOJ.zip_Jugs A_ZOJ NTA_zoj acm_zoj acm 1216_zoj code

    【ZOJ.zip】是一个压缩包,里面包含了与ZOJ(Zhejiang Online Judge)相关的ACM(International Collegiate Programming Contest)题解。ZOJ是一个在线编程竞赛平台,它为参赛者提供了一系列算法题目进行练习,以...

    zoj1027解题指南

    【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...

    Problem Arrangement zoj 3777

    Problem Arrangement zoj 3777

    ZOJ题目答案源码

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...

    zoj 题库 详细解答 解题代码

    zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...

    ACM训练必备POJ ZOJ题目分类及解题思路

    学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路

    zoj.rar_zoj_zoj4041

    《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...

    zoj 700源代码

    ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...

    ZOJ1014.zip_zoj code_zoj1004

    标题“ZOJ1014.zip_zoj code_zoj1004”表明这是一个与ZOJ(ZeroJudge)在线判题系统相关的代码压缩包,其中可能包含了解决ZOJ问题1004的源代码。ZOJ是面向编程爱好者和学生的一个在线编程竞赛平台,它提供了各种算法...

    ZOJ月赛 题解 (ZOJ Monthly, August 2014)

    **ZOJ月赛题解 (ZOJ Monthly, August 2014)** ZOJ(Zhejiang Online Judge)是中国著名的在线编程竞赛平台之一,它为程序员和学生提供了丰富的算法练习和比赛机会。2014年8月的ZOJ月赛是一场面向广大编程爱好者的...

    zoj 1003c 语言的

    zoj 1003 c语言的,要写这么多描述吗。。

    zoj1951的AC代码

    本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够

    zoj 1140-zju 2433 简单题的部分答案

    标题 "zoj 1140-zju 2433 简单题的部分答案" 暗示了这是一个关于编程竞赛题目的解答集合,其中涵盖了ZOJ(浙江大学在线评测系统)上的两道题目——ZOJ 1140 和 ZJU 2433。这些题目可能属于算法或数据结构的范畴,...

    ZOJ1805代码

    ZOJ1805代码

    ZOJ题解集合-截至2835

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...

Global site tag (gtag.js) - Google Analytics