wcwswswws的日记

wcwswswws

sgu512 Friendly Points

    这道题还是浪费了一个上午……太久没切题都忘了考虑long long了……
    
    题意:在平面上给出n个不同的点,如果一对点构成的矩形上没有其他点就算是友好点对。求一共有多少友好点对。n<=10^5
    solution:
    分治。按x轴排序后分治,计算跨中线的点对。分成左右2边,都是从上到下排序的。我们考察右边的一点x,能和它组成友好点对的点具有单调性,具体的说就是从上往下看是单调递减,过了右边点x的高度后单调递增的,不在此序列中的点如果和x构成的矩形将包含一个序列内的点。如果我们只考虑单调递减的部分,那么左边的点可以用一个栈存。再考虑右边的点,我们还是只考虑在x上边的情况。能和x组成矩形的左边的点的上界要么为正无穷,要么就是在x所在的x坐标上或者左边的离轴最近的一点。这样,我们同样可以用一个栈去存。考虑在x下方的情况可以翻过来做,这样就解决了这个问题了。
     
      我知道我的表述可能有些问题,我就补充一下我想这题的思路好了:首先,我先发现了对于某个点,找他左边和他构成友好点对的点的单调性,想不到如何维护这个数据结构,但是想到如果我确定某条分割线之后线性维护栈来统计友好点的方法,最后把单调性和分割线这二个性质联系起来,就想到又有单调性又有分割线的分治了……

posted on 2011-10-22 12:37 世界厕所所长 阅读(411) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


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