POJ 2318 TOYS
分析:就是让你找每个盒子里面有几个玩具,由于坐标都是整数,处理更加简单,二分+叉积判断位置。
1 |
|
POJ 2398 Toy Storage
分析:和上一题差不多,就是多了一步排序,多加一个数组。
1 |
|
POJ 3304 Segments
分析:这题就是问是否存在一条直线,使得所有线段在这条直线上的投影存在至少一个公共点。
显然,投影在直线存在公共点,那么以公共点为垂足的这个直线的垂线肯定穿过所有线段,这个问题就转化为了是否存在一条直线和所有线段相交。那么枚举所有线段的端点任取两个作为直线就行了(可以自己画图看一下)。
有一点需要注意:在枚举端点时,如果两个端点的距离小于1e-8
就跳过去,因为在题目要求精度下,相当于零向量和其他向量叉积,这样的叉积出来就是0,算出来的结果肯定就错了。
1 |
|
POJ 1269 Intersecting Lines
分析:就是让求两个直线的交点,叉积判断平行和三点共线,利用直线的参数表示法求解交点。
注意⚠️:如果使用%.2lf
用C++
提交,%.2f
用G++
提交。
1 |
|
POJ 1556 The Doors
分析:就是一个房间有很多墙,让你求两个坐标之间的最短路。直接根据两点之间是否有墙建图(判断线段是否规范相交),然后跑个最短路。
1 |
|
POJ 2653 Pick-up sticks
分析:直接从前往后暴力判断。
1 |
|
POJ 1066 Treasure Hunt
分析:就是判断最少经过几个墙到达藏宝室。还是线段相交问题。
注意⚠️:n=0时直接输出1就行。
1 |
|
POJ 1410 Intersection
分析:可以直接判断线段相交+线段在矩形内,也可以判断投影+点的位置关系,还可以利用计算机图形学中的剪裁算法等。
若线段和矩形未通过快速排斥试验(Quick Rejection Test)**,则两者不可能相交。
反之,在通过QRT后,线段所在矩形一定与矩形有公共部分。
此时若线段所在直线与矩形任一对角线**相交,则线段一定与矩形区域相交。
1 |
|
POJ 1696 Space Ant
分析:由于数据较少,直接按照极角进行排序,反复找相对当前点极角最小的点。
1 |
|
POJ 3347 Kadj Squares
分析:首先计算出每个正方形的左边和右边顶点的横坐标,怎么求哪?就是枚举每个正方形前面的正方形,让当前的与前面的每个都算出一个正好贴紧的情况,其中只有一个是合法的(和其他的不相交的),就是那个横坐标最大的,所以每次求 $max$ 就行了,最后就是收缩被覆盖的正方形坐标,如果两个相邻的正方形大小不同,那么肯定存在覆盖关系,详细见图下代码:
1 |
|
POJ 2826 An Easy Problem?!
分析:被这题坑了好久啊,还是经验少,注意一下坑点:
- 特判平行(一般都能想到,但是我就是
wa
在了这点) - 在利用斜率计算线上点时注意斜率不存在的情况。
- 相交却装不了水有三种情况,详见代码
- 还有个
(sgn(p1.y-cp.y)==0&&(p1.x-cp.x)==0)||(sgn(p3.y-cp.y)==0&&(p3.x-cp.x)==0)
可能分析麻烦了,不过总算是过了。
1 |
|