HDU3465 树状数组逆序数

Life is a Line

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 1927 Accepted Submission(s): 471

Problem Description

There is a saying: Life is like a line, some people are your parallel lines, while others are destined to meet you.
Maybe have met, maybe just a matter of time, two unparallel lines will always meet in some places, and now a lot of life (i.e. line) are in the same coordinate system, in a given open interval, how many pairs can meet each other?

Input

There are several test cases in the input.

Each test case begin with one integer N (1 ≤ N ≤ 50000), indicating the number of different lines.
Then two floating numbers L, R follow (-10000.00 ≤ L < R ≤ 10000.00), indicating the interval (L, R).
Then N lines follow, each line contains four floating numbers x1, y1, x2, y2 (-10000.00 ≤ x1, y1, x2, y2 ≤ 10000.00), indicating two different points on the line. You can assume no two lines are the same one.

The input terminates by end of file marker.

Output

For each test case, output one integer, indicating pairs of intersected lines in the open interval, i.e. their intersection point’s x-axis is in (l, r).

Sample Input

0.0 1.0

0.0 0.0 1.0 1.0 0.0 2.0

1.0 2.0 0.0 2.5 2.5 0.0

Sample Output

Author

iSea @ WHU

Source

2010 ACM-ICPC Multi-University Training Contest（3）——Host by WHU

题意：

给出n条线段两个端点的坐标以及x轴的一个范围l,r，问在这个范围内直线有几个交点。

代码：

 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
",ans+tem*cnt);
77     }
78     return 0;
79 }