二维平面上N个点之间共有C(n,2)条连线。求这C(n,2)条线中斜率小于0的线的数量。
二维平面上的一个点，根据对应的X Y坐标可以表示为(X,Y)。例如：(2,3) (3,4) (1,5) (4,6)，其中(1,5)同(2,3)(3,4)的连线斜率 < 0，因此斜率小于0的连线数量为2。
Input第1行：1个数N，N为点的数量(0 <= N <= 50000)
第2 - N + 1行：N个点的坐标，坐标为整数。(0 <= Xii , Yii <= 10^9)Output输出斜率小于0的连线的数量。(2,3) (2,4)以及(2,3) (3,3)这2种情况不统计在内。Sample Input
4 2 3 3 4 1 5 4 6
Sample Output
2
选x或y，维护另一个的树状数组即可。
1 #include<iostream www.qwangxiao.com/k/gzwxkc/>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5
6 using namespace std;
7
8 const int maxn=60005;
9 int g[maxn],n;
10
11 struct node
12 {
13 int x,y;
14 int y1;
15 }c[maxn];
16
17 void update(int x)
18 {
19 for(;x<=n;x+=x&(-x))
20 g[x]++;
21 }
22
23 int getsum(int x)
24 {
25 int sum=0;
26 for(;x>0;x-=x&(-x))
27 sum+=g[x];
28 return sum;
29 }
30
31 bool cmpx(node xx,node yy)
32 {
33 if(xx.x!=yy.x)
34 return xx.x<yy.x;
35 return xx.y<yy.y;
36 }
37
38 bool cmpy(node xx,node yy)
39 {
40 if(xx.y!=yy.y)
41 return xx.y<yy.y;
42 return xx.x<yy.x;
43 }
44
45 int main()
46 {
47 scanf("%d",&n);
48 for(int i=1;i<=n;i++)
49 scanf("%d%d",&c[i].x,&c[i].y);
50
51 sort(c+1,c+n+1,cmpy);
52 for(int i=1;i<=n;i++)
53 c[i].y1=n-i+1;
54 sort(c+1,c+n+1,cmpx);
55 memset(g,0,sizeof(g));
56 long long ans=0;
57 for(int i=1;i<=n;i++)
58 {
59 ans+=getsum(c[i].y1);
60 update(c[i].y1);
61 }
62 printf("%lld\n",ans);
63
64
65 return 0;
66 }