- 浏览: 380168 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (229)
- java编程 (4)
- java实用程序 (2)
- 算法设计 (34)
- 数据库 (8)
- ACM模板 (12)
- 技术术语 (1)
- java_web (3)
- php (22)
- eclipse (3)
- linux (25)
- linux命令使用心得 (3)
- web服务器 (8)
- IT知识 (2)
- 前端技术 (17)
- 开源软件 (5)
- vim (3)
- linux多线程 (9)
- web开发经验 (3)
- lua (5)
- linux编程 (3)
- smarty (1)
- mysql (4)
- Hive (2)
- 数据挖掘 (9)
- python (2)
- 生活 (1)
- C++ (2)
- 计算机 (1)
- objective-c (11)
- css (2)
- 游戏 (1)
- Mac (1)
最新评论
-
lr544463316:
我的怎么不行呀.....
Mysql Access denied for user ''@'localhost' to database 的一种解决方法 -
babaoqi:
使用时需要注意group_concat函数返回值的最大长度=g ...
mysql中的group_concat函数 -
代码能力弱成渣:
可以帮我看下我的代码么?我自己写的sam,也有ac过题的,但是 ...
求两个字符串的最长公共连续子序列(SAM实现) -
atgoingguoat:
有1000个?不过还是收藏下。
jquery常用的插件1000收集(转载)
/* 其实就是把总共的 放置次数减去不能放置的那些就行了。而不能放置的 那部分是一个个矩形 ! 所以问题 就转化为举行并的面积了。 */ #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; }
发表评论
-
升序数组中求一个key出现的次数
2013-01-09 23:08 1069算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需 ... -
判断单链表是否有环
2013-01-08 19:07 888算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次 ... -
hdu3684
2011-11-15 20:11 894/* 刚开始打了个记录上下左右四个点的,一直tle。 ... -
hdu3686
2011-11-14 20:43 1006/* 无向图边的双连通分量,在同一个连通分量里的边之间 ... -
poj3968
2011-11-14 04:45 1379source: http://poj.org/problem ... -
uva2819
2011-11-13 02:20 864source: http://livearchive.onli ... -
manacher算法
2011-11-11 00:06 2412const int LEN=110005; const ... -
hdu4118
2011-11-09 21:53 1163枚举每条边最多被经过的次数即可 #include ... -
hdu4115
2011-11-09 16:27 999source: http://acm.hdu.edu.cn/ ... -
uva(Transitive Closure)
2011-11-08 14:45 884source: http://livearchive.onli ... -
zoj3500
2011-11-07 17:41 926求两个球的体积交或者并 #include <cs ... -
zoj3545
2011-11-04 18:18 842/* AC自动机 相当暴力的 解法: mark[i ... -
zoj3190
2011-11-04 17:34 1255/* * AC自动机,先对资源串和病毒串构成的字符串 ... -
zoj3228
2011-11-04 16:12 929/* * AC自动机,每个节点 添加一个d表示节点代 ... -
poj3691(DNA Repair)
2011-11-04 13:18 1454/* AC自动机,增设虚拟节点,求长度为n的字符串中包 ... -
hdu2825
2011-11-04 11:53 961/* AC自动机,增设虚拟节点,求长度为n的字符 ... -
hdu4095
2011-11-03 13:19 991/* 第一步,构建BST,用第一个数作为bst的 ... -
poj1741(树的分治,基于边的 分治)
2011-11-02 20:25 3327/* 树基于边的分治算法,计算树中距离小于等于k的点 ... -
hdu2939
2011-10-29 18:36 823source: http://acm.hdu.edu.cn/s ... -
hdu3982
2011-10-29 10:20 909//半平面交+多边形和圆的交的面积 #include ...
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
ZOJ1805代码
zoj1027解题指南和代码,还不错,是学校培训给的。
zoj吐血制作,希望大家喜欢
zoj4041正确题解源代码,以及运行程序
zoj 题库 详细解答 解题代码 acm
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
能AC 通过的c++代码,包括zoj1002,1091,1789
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载