国家集训队2005论文集
§1 问题的提出
§1.1 问题描述 [USACO 2.1 Shaping Regions改编]
N个不同颜色的不透明长方形(1≤N≤3000)被放置在一张长宽分别为A、B的白纸上。这些长方形被放置时,保证了它们的边与白纸的边缘平行。所有的长方形都放置在白纸内,所以我们会看到不同形状的各种颜色。坐标系统的原点(0,0),设在这张白纸的左下角,而坐标轴则平行于纸边缘。
输入:
第1行:A , B 和 N, 由空格分开。
第2~N+1行:按照从下往上的顺序,每行输入的是一个长方形的放置。为五个数 llx, lly, urx, ury, color 这是长方形的左下角坐标,右上角坐标和颜色。其中color为整数。0<=llx,urx<=A,0<=lly,ury<=B。所有坐标(包括A、B)都是0至10^9的实数。
颜色 1和底部白纸的颜色相同。
输出:
输出文件应该包含一个所有能被看到颜色连同该颜色的面积(保留小数点后三位)的列表(即使颜色的编号不是连续的)。按color的增序顺序输出,不要输出面积为0的颜色。
样例输入:
20 20 3 2 2 18 18 2 0 8 19 19 3 8 0 10 19 4
样例输出
1 91.000 2 84.000 3 187.000 4 38.000
§1.2 问题的初步分析——离散化
自IOI1998的Picture问题始,和平面放置矩形有关的问题已在信息学竞赛中屡见不鲜,其最基本的预处理操作是将平面离散化。如图1
国家集训队2005论文集 王... 39页 免费喜欢此文档的还喜欢 国家集训队2006...朱泽园 问题一的提出 USACO Shaping Regions 改编 N个不同颜色的不透明长方形(...
国家集训队2005论文集 朱泽... 27页 免费 国家集训队2004论文集 楼天......链接无效.: 第 11 页共 23 页 IOI2004 国家集训队论文 朱泽园 a b a b...
国家集训队2006论文集 贾... 20页 免费 国家集训队2006论文集 汤... 11... China 朱泽园, 高三, 南京市外国语学校, 江苏, 中国 2005-12-29 Keywords:...
国家集训队1999论文集 陈... 国家集训队1999论文集 来... 国家集训队1999... China 朱泽园, 高三, 南京市外国语学校, 江苏, 中国 2005-12-29 Keywords:...
国家集训队2006论文集_朱泽... 10页 5财富值 国家集训队2005论文集 朱泽.... 多串匹配算法 及其启示南京市外国语学校朱泽园 问题提出所谓多串匹配,就是给定...
《浅谈数形结合思想在信息学竞赛中的应用》朱泽园:《多串匹配算法及其启示》 国家集训队2005论文集 蒋炎岩:《数据结构的联合——块状链表》金恺:《杂题大拼盘》...
历年国家集训队论文题目 发信站: 日月光华 (2005年06月11日20:31:11 星期...朱泽园 - 多串匹配算法及其启示 韩文弢 - 论C++语言在信息学竞赛中的应用 ...
国家集训队论文分类_计算机软件及应用_IT/计算机_...2005 2003 2003 2006 2005 2006 2007 2008 2001 ...《半平面交的算法及其应用》 朱泽园:《半平面交的...
热门文档