文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 国家集训队2005论文集 朱泽园
侵权投诉

国家集训队2005论文集 朱泽园

国家集训队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

上一页第3页

热门文档

相关文档

  • 国家集训队2005论文集 朱泽园

    国家集训队2005论文集 王... 39页 免费喜欢此文档的还喜欢 国家集训队2006...朱泽园 问题一的提出 USACO Shaping Regions 改编 N个不同颜色的不透明长方形(...

  • 国家集训队2004论文集 朱泽园

    国家集训队2005论文集 朱泽... 27页 免费 国家集训队2004论文集 楼天......链接无效.: 第 11 页共 23 页 IOI2004 国家集训队论文 朱泽园 a b a b...

  • 国家集训队2006论文集_朱泽园

    国家集训队2006论文集 贾... 20页 免费 国家集训队2006论文集 汤... 11... China 朱泽园, 高三, 南京市外国语学校, 江苏, 中国 2005-12-29 Keywords:...

  • 国家集训队2006论文集 朱泽园

    国家集训队1999论文集 陈... 国家集训队1999论文集 来... 国家集训队1999... China 朱泽园, 高三, 南京市外国语学校, 江苏, 中国 2005-12-29 Keywords:...

  • 国家集训队2004论文集 朱泽园

    国家集训队2006论文集_朱泽... 10页 5财富值 国家集训队2005论文集 朱泽.... 多串匹配算法 及其启示南京市外国语学校朱泽园 问题提出所谓多串匹配,就是给定...

  • 中国国家集训队论文集目录(1999-2009)

    《浅谈数形结合思想在信息学竞赛中的应用》朱泽园:《多串匹配算法及其启示》 国家集训队2005论文集 蒋炎岩:《数据结构的联合——块状链表》金恺:《杂题大拼盘》...

  • 国家集训队论文目录

    历年国家集训队论文题目 发信站: 日月光华 (2005年06月11日20:31:11 星期...朱泽园 - 多串匹配算法及其启示 韩文弢 - 论C++语言在信息学竞赛中的应用 ...

  • 国家集训队论文分类

    国家集训队论文分类_计算机软件及应用_IT/计算机_...2005 2003 2003 2006 2005 2006 2007 2008 2001 ...《半平面交的算法及其应用》 朱泽园:《半平面交的...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email