Hint
上图是样例的解释 , 交点是A,B,C
【cdoj1341卿学姐与城堡的墙】思路:
文章插图
对所有直线进行预处理(只保存和uv的交点)这是很容易想到的 , 不过一开始不知道有种东西叫逆序对 , 只想到n*n的算法 。。。。。。。
逆序对的求法有好几种我用的是归并的方法 。。
不过这个题要考虑边界情况 , 如果按u边界的y排序的话 , 就需要对u边界上的点特殊处理 , 其实就是u边界上的点扫一遍就好了 , , ,
1 #include
2 #include3 #include 4 #include 5 #include 6 #include 7 #include8 #include