学步园

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3128

题意：给你n条直线（n<=10000），求（l,r）区间内的交点个数

解法：每条直线分别与x=l  和  x=r求交点，这样就转换成了 n条线段  两端点在x=l 和x =r上，求有几个交点，这样就转换成了求逆序数的问题了

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const double eps = 1e-8;
const int maxn = 10010;
int c[maxn],ans;
void update(int x,int d){
	for(;x>0;x-=x&-x)  c[x]+=d;
}
int sum(int x){
	for(ans=0;x<maxn;x+=x&-x)  	ans+=c[x];
	return ans;
}
struct point {
	double x,y;
};
struct L{
	point a,b;
	double h1,h2;
	int id;
}in[maxn];
int tmp[maxn];
int cmp(L x,L y){
	if(fabs(x.h1-y.h1)<eps)  return x.h2<y.h2;
	return x.h1<y.h1;
}
int cmp2(L x,L y){
	if(fabs(x.h2-y.h2)<eps)  return x.h1<y.h1;
	return x.h2<y.h2;
}
int main(){
	int n;
	double l,r;
	while(scanf("%d",&n)!=EOF){
		for(int i=1;i<=n;i++)	scanf("%lf%lf%lf%lf",&in[i].a.x,&in[i].a.y,&in[i].b.x,&in[i].b.y);
		scanf("%lf%lf",&l,&r);
		for(int i=1;i<=n;i++){
			double k=(in[i].b.y-in[i].a.y)/(in[i].b.x-in[i].a.x);
			in[i].h1=k*(l-in[i].a.x)+in[i].a.y;
			in[i].h2=k*(r-in[i].a.x)+in[i].a.y;
		}
		sort(in+1,in+n+1,cmp);
		for(int i=1;i<=n;i++)	in[i].id=i;
		sort(in+1,in+n+1,cmp2);
		for(int i=1;i<=n;i++) tmp[in[i].id]=i;
		memset(c,0,sizeof(c));
		int s=0;
		for(int i=1;i<=n;i++){
			s+=sum(tmp[i]+1);
			update(tmp[i],1);
		}
		printf("%d\n",s);
	}
	return 0;
}