矩形切割与动态统计问题的一些ACM例题

矩矩 形形 切切 割割 与与 动动 态态 统统 计计 问问 题题 矩形切割具体思想见薛矛的矩形切割具体思想见薛矛的 解决动态统计问题的两把利刃解决动态统计问题的两把利刃 矩形切割例题 矩形切割例题 POJ 2528 3277 1151 1389 1177 POJ 2528 Mayor s poster 题意 贴海报 后一张海报一定不会被前面的海报覆盖 海报覆盖区域用 x y 区间表示 问最后有多少张海报是没被完全覆盖的 Code include include using namespace std define maxn 10005 struct NODE int x y int ans node maxn int n void cover int l int r int k int c while k n if k n if k n r l 1 0 node c ans r l 1 return if lnode k y 左边部分被覆盖 cover node k y 1 r k 1 c r node k y int main int t i j sum scanf d while t sum 0 memset node 0 sizeof node scanf d for i 0 i 0 i cover node i x node i y i 1 i for i 0 i0 sum printf d n sum return 0 Sample Input 1 5 1 4 2 6 8 10 3 4 7 10 Sample Output 4 POJ 3277 City Horizon 题意 一些大楼都在地平线上 求这些大楼倒影覆盖总面积 分析 水平线上被覆盖的部分肯定记录到高度大的部分 所以按大楼高度升序排序 Code include include include using namespace std define maxn 40005 struct NODE int64 x1 x2 y ans node maxn int n bool cmp NODE a NODE b if a y b y return a y b y 因为是面积和的问题 所以 宽高的肯定应该放在后面 低的算被覆盖 else if a x2 b x2 return a x2b x1 void cover int64 l int64 r int k int c while k n if k n r l 0 node c ans r l return if lnode k x2 cover node k x2 r k 1 c int main int i j memset node 0 sizeof node scanf d for i 0 i 0 i cover node i x1 node i x2 i 1 i int64 sum 0 for i 0 i 1 sum node i ans node i y printf I64d n sum Sample Input 4 2 5 1 数据分别为水平线上起点和终点 楼的高度 9 10 4 6 8 2 4 6 3 Sample Output 16 POJ 1151 AtlantisAtlantis 矩形面积并 矩形面积并 法 1 离散化 本题数据量为 100 以内 离散化后坐标纸上最大为 100 100 的网格 将被覆盖的网格标记为 true 之后直接扫描统计即可 Code include include include include include using namespace std define maxn 205 struct NODE double x1 y1 x2 y2 node maxn double x maxn y maxn bool map maxn maxn int main int n i j k t 0 while scanf d for i 0 i n i scanf lf lf lf lf x m node i x1 y m node i y1 m x m node i x2 y m node i y2 m printf m d n m sort x x m sort y y m memset map false sizeof map int x1 x2 y1 y2 for i 0 i n i 离散化 for j 0 j m j if fabs x j node i x1 1e 6 x1 j break for j 0 j m j if fabs x j node i x2 1e 6 x2 j break for j 0 j m j if fabs y j node i y1 1e 6 y1 j break for j 0 j m j if fabs y j node i y2 1e 6 y2 j break for j x1 j x2 j for k y1 k y2 k map j k true printf Test case d n t double ans 0 0 for i 0 i m 1 i for j 0 j m 1 j if map i j 被覆盖的求 出面积ans x i 1 x i y j 1 y j printf Total explored area 2lf n n ans return 0 法 2 普通矩形切割法 将每个矩形着色 假设后面的矩形颜色一定不会被 前面的矩形颜色覆盖 最后扫描个每种颜色覆盖的区域 总和便是所求 Code include include include include using namespace std define maxn 105 struct NODE double x1 y1 x2 y2 int color node maxn double map maxn int n void cover double x1 double y1 double x2 double y2 int c int k while knode k x2 x2n ode k y2 y2 n fabs x2 x1 1e 6 fabs y2 y1 1e 6 map c x2 x1 y2 y1 return if x1 node k x2 偏右 cover node k x2 y1 x2 y2 c k 1 x2 node k x2 if y1 node k y2 偏上 cover x1 node k y2 x2 y2 c k 1 y2 node k y2 int main int i t 0 while scanf d for i 0 i 0 i cover node i x1 node i y1 node i x2 node i y2 n ode i color i 1 double ans 0 0 for i 0 i1e 6 ans map i printf Test case d nTotal explored area 2lf n n t ans return 0 SampleSample InputInput 2 10 10 20 20 15 15 25 25 5 0 SampleSample OutputOutput Test case 1 Total explored area 180 00 POJPOJ 11771177 矩形周长并 括号匹配 矩形周长并 括号匹配 矩形切割 矩形切割 分析 括号匹配 首先把矩形的上边界作为 左括号 边 下边界作为 右括 号 边 然后上下排序 假定排完序之后是下面的状态 考虑 最外侧 的括号的数量 显然上面的那个串是 define maxn 10005 struct NODE int cankao weizhi st en weizhi 为表明匹配边 nodex maxn nodey maxn int mapx 2 maxn mapy 2 maxn lenx maxn leny maxn vist maxn bool cmp NODE n1 NODE n2 return n1 cankao n2 cankao int main int n i j x1 y1 x2 y2 memset mapx 0 sizeof mapx memset mapy 0 sizeof mapy scanf d for i 0 i n i 存信息 scanf d d d d x1 maxn y1 maxn x2 maxn y2 maxn mapx x1 mapx x2 mapy y1 mapy y2 1 nodex 2 i cankao y1 nodex 2 i weizhi 1 nodex 2 i st x1 nodex 2 i en x2 nodex 2 i 1 cankao y2 nodex 2 i 1 weizhi 1 nodex 2 i 1 st x1 nodex 2 i 1 en x2 nodey 2 i cankao x1 nodey 2 i weizhi 1 nodey 2 i st y1 nodey 2 i en y2 nodey 2 i 1 cankao x2 nodey 2 i 1 weizhi 1 nodey 2 i 1 st y1 nodey 2 i 1 en y2 stable sort nodex nodex 2 n cmp stable sort nodey nodey 2 n cmp int tmpx 0 tmpy 0 ans 0 for i 0 i 2 maxn i if mapx i mapx i tmpx lenx tmpx i if mapy i mapy i tmpy leny tmpy i for i 0 i 2 n i 离散化 nodex i st mapx nodex i st nodex i en mapx nodex i en nodey i st mapy nodey i st nodey i en mapy nodey i en memset vist 0 sizeof vist for i 0 i 2 n i for j nodex i st j nodex i en j vist j nodex i weizhi if vist j 0 匹配成功 ans lenx j 1 lenx j memset vist 0 sizeof vist for