卿学姐与城堡的墙

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

卿学姐终于来到了魔王的城堡，城堡修建的十分壮观。

即使心中放不下公主，卿学姐还是忍不住驻足观赏这宏伟的建筑。

卿学姐注意到城堡的墙上有若干直线状的花纹。

可以将墙看做一个平面，卿学姐想知道有多少种方式任取两个直线，使得这两个直线的交点的横坐标

Input

第一行三个整数

接下来有

输入保证

Output

输出一个整数，代表选择的方法数。

Sample input and output

Sample Input	Sample Output
3 -3 1 -1 3 2 2 1 1	3

Hint

title

上图是样例的解释，交点是A,B,C

思路：

对所有直线进行预处理（只保存和uv的交点）这是很容易想到的，不过一开始不知道有种东西叫逆序对，只想到n*n的算法。。。。。。。

逆序对的求法有好几种我用的是归并的方法。。

不过这个题要考虑边界情况，如果按u边界的y排序的话，就需要对u边界上的点特殊处理，其实就是u边界上的点扫一遍就好了，，，

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <queue>
 7 #include <stack>
 8 #include <map>
 9 #include <vector>
10 #include <cstdlib>
11 #include <string>
12 
13 #define PI acos((double)-1)
14 #define E exp(double(1))
15 using namespace std;
16 
17 vector<pair<long long ,long long > >p;
18 long long  a[200000+5];
19 long long  temp[200000+5];
20 long long  cnt=0;//逆序对的个数
21 double cnm_lg(int n,int m)
22 {
23     int i;
24     double s1=0.0,s2=0.0;
25     for(i=1;i<=m;i++)
26         s1 += log(i);
27     for(i=n-m+1;i<=n;i++)
28         s2 += log(i);
29     return s2-s1;
30 }
31 long long  cnm_double(int n,int m)
32 {
33     if(n<m)
34         return 0;
35     if(m > n/2)
36     m = n-m;
37     return (long long)exp(cnm_lg(n,m));
38 }
39 void merge(int left,int mid,int right)
40 {
41     int i=left,j=mid+1,k=0;
42     while (( i<=mid )&& (j<=right))
43           if (a[i]<a[j]) temp[k++]=a[i++];
44           else {
45               cnt+=mid+1-i;//关键步骤
46               temp[k++]=a[j++];
47           }
48     while (i<=mid) temp[k++]=a[i++];
49     while (j<=right) temp[k++]=a[j++];
50     for (i=0,k=left; k<=right;) a[k++]=temp[i++];
51 }
52 void mergeSort(int left,int right)
53 {
54     if (left<right)
55     {    int mid=(left+right)/2;
56          mergeSort(left, mid);
57          mergeSort(mid+1, right);
58          merge(left, mid, right);
59     }
60 }
61 int main (void)
62 {
63     int n,u,v;
64     cin>>n>>u>>v;
65     for(int i=0;i<n;i++)
66     {
67         long long k,b;
68         scanf("%lld%lld",&k,&b);
69         p.push_back(make_pair(b+u*k,b+v*k));
70     }
71     sort(p.begin(),p.end());
72     p.push_back(make_pair(0,1000000000));
73     pair<long ,long >temp=p[0];
74     temp.second=0;
75     for(int i=1;i<=n;i++)
76         if(temp.first != p[i].first || i==n)
77         {
78             cnt+=cnm_double(i-temp.second,2);
79             temp.first=p[i].first;temp.second=i;
80         }
81     if(u==v)
82     {
83         cout<<cnt<<endl;return 0;
84     }
85     for(int i=0;i<n;i++)
86         a[i]=p[i].second;
87     mergeSort(0,n-1);
88     cout<<cnt<<endl;
89     return 0;
90 }

View Code