伦伦刚刚在高中学习了解析几何，学会了计算两条直线的交点。这天，老师给她布置了一道作业。在平面上有 n 条直线，他们之间有若干交点。给定一对平板（两条平行的直线），问这有多少对直线，他们的交点在这一对平板之间（注意 (i, j) 和 (j, i) 只算一对）。
（还记得一道河两边的什么鬼的逆序对的题吗？）
我们设一对平板的代号分别为X、Y。
对于每一条直线，我们可以解出它在X、Y上的交点的横坐标，用一个struct T存下来。
我们按照X上面的交点横坐标排序T
然后给T在Y上面的交点横坐标做归并排序，逆序对个数就是焦点个数，而一个焦点就对应了一对合法直线，所以答案就是逆序对个数。
为什么逆序对个数是焦点个数？
因为X上面的坐标排列是有序的，从小到大的。对于Y上面的坐标，如果出现一个逆序对，他们一定能够产生焦点（可以自己画图验证一下）。
附上AC代码
#include<cstdio> #include<algorithm> using namespace std; template<class T> inline void read(T &_a){ bool f=0;int _ch=getchar();_a=0; while(_ch<‘0‘ || _ch>‘9‘){if(_ch==‘-‘)f=1;_ch=getchar();} while(_ch>=‘0‘ && _ch<=‘9‘){_a=(_a<<1)+(_a<<3)+_ch-‘0‘;_ch=getchar();} if(f)_a=-_a; } const int maxn=100001; int n; long long ans; struct node { double x1,x2; inline bool operator < (const node x) const {return x1<x.x1;} }res[maxn]; double k1,a1,b1,k,b,T[maxn]; void merge(int l,int r) { if(l==r) return; int mid=(l+r)>>1; merge(l,mid); merge(mid+1,r); int i=l,j=mid+1,q=l; while(i<=mid&&j<=r) { if(res[i].x2>res[j].x2) { ans+=mid-i+1; T[q++]=res[j++].x2; } else T[q++]=res[i++].x2; } while(i<=mid) T[q++]=res[i++].x2; while(j<=r) T[q++]=res[j++].x2; for (register int i=l;i<=r;++i) res[i].x2=T[i]; } int main() { freopen("point.in","r",stdin); freopen("point.out","w",stdout); scanf("%lf%lf%lf",&k1,&a1,&b1); read(n); for (register int i=1;i<=n;++i) { scanf("%lf%lf",&k,&b); res[i].x1=(b-b1)/(k1-k); res[i].x2=(b-a1)/(k1-k); } sort(res+1,res+n+1); merge(1,n); printf("%lld",ans); return 0; }
直线的交点 计蒜客提高组模拟赛（三）Day2 逆序对 归并排序
原文：http://www.cnblogs.com/jaywang/p/7748447.html