对于题中所给的任意两条公路,如果要相交的话,那么(设他们的序号对分别是(a,b),(c,d))(a-c)*(b-d) < 0。这个是一定成立的。也就是说如果在一个岛
屿中它序号比和它相交的那条公路的序号大的话,那么在另外一个岛屿中,一定比和它相交的那条公路的序号小。
这样的话,我们就可以对一边进行排序(从大到小,如果相等再按另外一边从大到小),这样处理之后,就可以对另外一边进行树状数组的操作了(这里用到了
上面的那么不等式)。到这基本思路已经OK了,不过结果一定要保存为__int64 或者long long
代码如下(建议自己先想)
CODE