题意描述:
求若干条线段交叉点的个数。题目保证不会有两条以上的线段交与一点。
乍一看还以为是计算几何的东西,其实不然,题目的条件限制使得这一题很简单。我们把题目描述的地图想象为笛卡尔坐标系上的点,可以规定,两边岸上的点都有相同的x值(分别为x0,x1且x0<x1),这样,如果x0,x1所夹范围内存在相交的两条线段l1、l2的话,假设他们与x0,x1交点的y值分别为l1y0,l1y1和l2y0,l2y1,那么这两条线段必须满足以下简单条件:(l1y0-l2y0)*(l1y1-l2y1)<0。也就是说,在直线x0上和x1上,l1、l2的y值大小顺序是相反的,这让我们联想到了逆序对。
具体做法是:
先将每条线段按x0对应的y值排序(我称之为第一次排序),然后根据x1对应的y值求出逆序对的个数,既是交叉点的个数。求逆序对的方法最直接的就是在冒泡排序是记录交换的次数,不过这样会超时,改进的算法是利用归并排序,在每次归并的时候统计逆序对个数(注意两个数相等的情况,当两数相等时它们不是逆序对)。
注意:在第一次排序中,因为不同线段的y值可能是相等的,这种情况下我们要依据x1对应的y值排序。忽略这种情况会导致计算的逆序对个数增多。
逆序对参阅:http://www.cppblog.com/hoolee/archive/2012/07/18/184090.html
做的好艰辛,感谢冰冰学长。
以下是本题代码:

posted on 2012-08-13 15:04 小鼠标 阅读(1304) 评论(1)  编辑 收藏 引用 所属分类: 排序

FeedBack:
# re: zoj3129--逆序对
2012-08-14 15:18 | 小鼠标
@tb
欢迎交流学习!  回复  更多评论
  

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


<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜