cdoj1341卿学姐与城堡的墙

Hint
上图是样例的解释，交点是A,B,C
【cdoj1341卿学姐与城堡的墙】思路：

文章插图
对所有直线进行预处理（只保存和uv的交点）这是很容易想到的，不过一开始不知道有种东西叫逆序对，只想到n*n的算法。。。。。。。
逆序对的求法有好几种我用的是归并的方法。。
不过这个题要考虑边界情况，如果按u边界的y排序的话，就需要对u边界上的点特殊处理，其实就是u边界上的点扫一遍就好了，，，
1 #include 2 #include3 #include 4 #include 5 #include 6 #include 7 #include8 #include 9 #include 10 #include 11 #include 12 13 #define PI acos((double)-1)14 #define E exp(double(1))15 using namespace std;16 17 vectorlong long ,long long > >p;18 long longa[200000+5];19 long longtemp[200000+5];20 long longcnt=0;//逆序对的个数21 double cnm_lg(int n,int m)22 {23int i;24double s1=0.0,s2=0.0;25for(i=1;i<=m;i++)26s1 += log(i);27for(i=n-m+1;i<=n;i++)28s2 += log(i);29return s2-s1;30 }31 long longcnm_double(int n,int m)32 {33if(n n/2)36m = n-m;37return (long long)exp(cnm_lg(n,m));38 }39 void merge(int left,int mid,int right)40 {41int i=left,j=mid+1,k=0;42while (( i<=mid )&& (j<=right))43if (a[i]];44else {45cnt+=mid+1-i;//关键步骤46temp[k++]=a[j++];47}48while (i<=mid) temp[k++]=a[i++];49while (j<=right) temp[k++]=a[j++];50for (i=0,k=left; k<=right;) a[k++]=temp[i++];51 }52 void mergeSort(int left,int right)53 {54if (left>n>>u>>v;65for(int i=0;itemp=p[0];74temp.second=0;75for(int i=1;i<=n;i++)76if(temp.first != p[i].first || i==n)77{78cnt+=cnm_double(i-temp.second,2);79temp.first=p[i].first;temp.second=i;80}81if(u==v)82{83cout< View Code