Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 1927 Accepted Submission(s): 471
1 /* 2 两直线在l,r之内有交点当且仅当(a1-a1)*(b1-b2)<0,a1,b1是其中一条直线与l,r的两个交点,这样按照a排一次序 3 只要b有交错就会有交点,然后就转化成求逆序数,先按照a从小到大排,给他们编一个号,在按照b从小到大排序 4 这样只要求编号的逆序数即可。特殊情况是直线平行y轴,此时他与其他的不平行于y轴的直线都相交。 5 求逆序数是当前的数的位置减去前面比他小的数的个数也就是正序数个数。 6 */ 7 #include<iostream> 8 #include<cstdio> 9 #include<cstring> 10 #include<algorithm> 11 using namespace std; 12 int A[50004]; 13 struct Lu 14 { 15 double a,b; 16 int num; 17 }L[50004]; 18 bool cmp1(Lu x,Lu y) 19 { 20 if(x.a==y.a) 21 return x.b<y.b; 22 return x.a<y.a; 23 } 24 bool cmp2(Lu x,Lu y) 25 { 26 if(x.b==y.b) 27 return x.a<y.a; 28 return x.b<y.b; 29 } 30 int lowbit(int id) 31 { 32 return id&(-id); 33 } 34 void add(int id,int v) 35 { 36 while(id<=50000){ 37 A[id]+=v; 38 id+=lowbit(id); 39 } 40 } 41 int qury(int id) 42 { 43 int s=0; 44 while(id>0){ 45 s+=A[id]; 46 id-=lowbit(id); 47 } 48 return s; 49 } 50 int main() 51 { 52 int n; 53 double l,r,x1,x2,y1,y2; 54 while(scanf("%d",&n)!=EOF){ 55 scanf("%lf%lf",&l,&r); 56 int ans=0,tem=0,cnt=0; 57 for(int i=0;i<n;i++){ 58 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 59 if(x1==x2){ //在l,r以外就去掉,在l,r以内要计算,就是这里wa到吐血。 60 if(x1>l&&x1<r) tem++; 61 continue; 62 } 63 L[cnt].a=y2+(y1-y2)*(l-x2)/(x1-x2); 64 L[cnt++].b=y2+(y1-y2)*(r-x2)/(x1-x2); 65 } 66 sort(L,L+cnt,cmp1); 67 for(int i=0;i<cnt;i++){ 68 L[i].num=i+1; 69 } 70 sort(L,L+cnt,cmp2); 71 memset(A,0,sizeof(A)); 72 for(int i=0;i<cnt;i++){ 73 add(L[i].num,1); 74 ans+=(i-qury(L[i].num-1)); //求逆序数 75 } 76 printf("%d\n",ans+tem*cnt); 77 } 78 return 0; 79 }
原文:http://www.cnblogs.com/--ZHIYUAN/p/6230742.html