wujiawei@HIT

ACM -- Fighting

常用链接

统计

最新评论

两个几何 ZOJ 3376 && ZOJ 3379

ZOJ 3376 Safest Points

题目大意:给平面上一些点,以及从这点出发的射线的方向。对于平面上的整点,

首先定义危险的点为平面上距离射线曼哈顿距离小于1的整点。要求求出距离危险点最远的整点的坐标,若有多个则按字典序排序。

 

我的做法:首先要注意距离射线曼哈顿距离小于1的可以这样判断,即判断射线与整点区间的交点,若在整点之间就说明这周围的顶点都是危险点,例:

                 

       其中A点上下两个点就为危险点,只需求出根据x坐标递增或递减,

根据射线的方程求A点的纵坐标,分别取上整和下整,然后将这些点标记为危险点。再以y坐标递增或递减,对x采取同样的做法,标记危险点,这样的两次是为了保证边界的情况。

求出所有危险点之后,进行一次BFS就可以得到答案。

总结:开始错在边界上了,要考虑到起点不在整点上以及注意dxdy方向

 

 

ZOJ 3379 Master Spark

题目大意:给出以原点为顶点的抛物线,平面上有若干点,求出一个角度能打到的点最多,输出这个数目。

我的做法:对每个点判断抛物线旋转到什么极角时能打得到,就是每个点对应的抛物线的极角区间,然后统计哪个极角区间覆盖次数最多即可。

 

这两道题都是浙大月赛的题,有事没做,后来队友说有两道几何让我做。。- -|||觉得题目很好的,前面那个题一开始就想的差不多,后来敲完发现问题改完就过了,后面那个倒是卡了好久,主要是极角上的问题,按区间左右分开处理加标记就不对,改成按区间两端点存就不对,不知道为啥,大概是精度的问题吧,以后注意吧哈哈,加油!

posted on 2010-08-24 19:52 wujiawei 阅读(342) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理