對于題中所給的任意兩條公路，如果要相交的話，那么(設他們的序號對分別是(a,b),(c,d))(a-c)*(b-d) < 0。這個是一定成立的。也就是說如果在一個島
 嶼中它序號比和它相交的那條公路的序號大的話，那么在另外一個島嶼中，一定比和它相交的那條公路的序號小。
 這樣的話，我們就可以對一邊進行排序(從大到小，如果相等再按另外一邊從大到小)，這樣處理之后，就可以對另外一邊進行樹狀數組的操作了(這里用到了
上面的那么不等式)。到這基本思路已經OK了，不過結果一定要保存為__int64 或者long long
 代碼如下(建議自己先想)

CODE
 1/**//*
 2  ID:Klion
 3  PROG:POJ_3067
 4  LANG:C
 5  樹狀數組，記得用__int64
 6 */
 7#include <stdio.h>
 8#include <stdlib.h>
 9#include <string.h>
10typedef struct
11{
12     int a,b;
13}BRI;
14BRI bri[1000006];//輸入數據的數組
15int tree[1000006];//樹狀數組
16int cmp(const void *e,const void *f)
17{//按b從大到小(若相等則按a從大到小) 排序的模板
18      BRI *c = (BRI *)e;
19      BRI *d = (BRI *)f;
20      if(c->b == d->b)
21          return d->a-c->a;
22      return d->b-c->b;
23}
24void update(int x,int val)
25{//更新某個點的值
26       while(x <= 1000006)
27          {
28              tree[x] += val;
29              x += (x & -x);
30          }
31       return ;
32}
33int read(int x)
34{//得到tree[1]-tree[x]的和
35      int ret = 0;
36      while(x > 0)
37        {
38            ret += tree[x];
39            x -= (x & -x);
40        }
41      return ret;
42}
43int main(void)
44{
45      freopen("3067.in","r",stdin);
46      freopen("3067.out","w",stdout);
47      int t;
48      int n,m,k;
49      int i,j;
50      __int64 sum;
51      scanf("%d",&t);
52      for(i = 1;i <= t;i++)
53        {
54            scanf("%d%d%d",&n,&m,&k);
55            for(j = 0;j < k;j++)
56             scanf("%d%d",&bri[j].a,&bri[j].b);
57          qsort(bri,k,sizeof(bri[0]),cmp);//排序，按b從大到小排序，如果b相等的話，再按a從大到小排序
58          memset(tree,0,sizeof(tree));
59          sum = 0;
60          for(j = 0;j < k;j++)
61            {//樹狀數組的操作
62                sum += read(bri[j].a-1);//得到已經插入過的直線中比這條直線的a小的直線的條數，也就是和這條直線相交的結果                update(bri[j].a,1);//對這條直線進行插入操作
63            }
64          printf("Test case %d: %I64d\n",i,sum);
65        }
66    return 0;
67}
68