ZOJ 3376 Safest Points
题目大意:给平面上一些点,以及从这点出发的射线的方向。对于平面上的整点,
首先定义危险的点为平面上距离射线曼哈顿距离小于1的整点。要求求出距离危险点最远的整点的坐标,若有多个则按字典序排序。
我的做法:首先要注意距离射线曼哈顿距离小于1的可以这样判断,即判断射线与整点区间的交点,若在整点之间就说明这周围的顶点都是危险点,例:
其中A点上下两个点就为危险点,只需求出根据x坐标递增或递减,
根据射线的方程求A点的纵坐标,分别取上整和下整,然后将这些点标记为危险点。再以y坐标递增或递减,对x采取同样的做法,标记危险点,这样的两次是为了保证边界的情况。
求出所有危险点之后,进行一次BFS就可以得到答案。
总结:开始错在边界上了,要考虑到起点不在整点上以及注意dx,dy方向
ZOJ 3379 Master Spark
题目大意:给出以原点为顶点的抛物线,平面上有若干点,求出一个角度能打到的点最多,输出这个数目。
我的做法:对每个点判断抛物线旋转到什么极角时能打得到,就是每个点对应的抛物线的极角区间,然后统计哪个极角区间覆盖次数最多即可。
这两道题都是浙大月赛的题,有事没做,后来队友说有两道几何让我做。。- -|||觉得题目很好的,前面那个题一开始就想的差不多,后来敲完发现问题改完就过了,后面那个倒是卡了好久,主要是极角上的问题,按区间左右分开处理加标记就不对,改成按区间两端点存就不对,不知道为啥,大概是精度的问题吧,以后注意吧哈哈,加油!