zoj 3157 Weapon 线段树求逆序对数

题目链接：http://www.icpc.moe/onlinejudge/showProblem.do?problemId=3128

题意：平面上有n条直线，给出l, r，求出这些直线的交点横坐标在(l, r)范围内的个数。

思路：

首先求出每条直线与直线x = l和直线x = r的交点，如下图。

因为题目要求区间(l, r)是开区间，所以为了避免交点的横坐标刚好是l或者r的情况，可以先把l加上一个很小的值，r减去一个很小的值，如图中的灰线。

然后求出各条直线与两条灰线的交点，首先按与l的交点的y值从小到大排序，然后标上一个id。

然后再按与r的交点的y值从小到大排序。

如果两条直线line1和line2，如果line1.ly < line2.ly，则如果line1.ry > line2.ry，那么这个交点肯定落在范围内。

所以此时排序后的id序列是3 1 2，很明显就是求这个序列的逆序对数。然后用线段树求出逆序对数就可以了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 #define maxn 10010
 5 #define eps 1e-8
 6 #define lson l, m, rt<<1
 7 #define rson m+1, r, rt<<1|1
 8 struct Line
 9 {
10     double k, b;
11     Line(double kk, double bb){k = kk; b = bb;}
12     Line(){}
13 }l[maxn];
14 double L, R;
15 struct Node
16 {
17     double l, r;
18     int id;
19     Node(double ll, double rr, int ii){l = ll; r = rr; id = ii;}
20     Node(){}
21 }node[maxn];
22 bool cmp1(Node a, Node b){return a.l < b.l;}
23 bool cmp2(Node a, Node b){return a.r < b.r;}
24 int sum[maxn<<2];
25 void pushup(int rt)
26 {
27     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
28 }
29 void build(int l, int r, int rt)
30 {
31     if(l == r) 
32     {
33         sum[rt] = 0; return;
34     }
35     int m = (l+r)>>1;
36     build(lson);
37     build(rson);
38     pushup(rt);
39 }
40 void update(int pos, int add, int l, int r, int rt)
41 {
42     if(l == r)
43     {
44         sum[rt] += add; return;
45     }
46     int m = (l+r)>>1;
47     if(pos <= m) update(pos, add, lson);
48     else update(pos, add, rson);
49     pushup(rt);
50 }
51 int query(int L, int R, int l, int r, int rt)
52 {
53     if(L <= l && r <= R) 
54     {
55         return sum[rt];
56     }
57     int m = (l+r)>>1;
58     int ret = 0;
59     if(L <= m) ret += query(L, R, lson);
60     if(R > m) ret += query(L, R, rson);
61     return ret;
62 }
63 int main() 
64 {
65    // freopen("in.txt", "r", stdin);
66     while(~scanf("%d", &n))
67     {
68         for(int i = 1; i <= n; i++)
69         {
70             double x1, y1, x2, y2;
71             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
72             double k = (y2-y1)/(x2-x1);
73             double b = y1 - k*x1;
74             l[i].k = k; l[i].b = b;
75         }
76         scanf("%lf%lf", &L, &R);
77         L += 1e-8; R -= 1e-8;
78         for(int i = 1; i <= n; i++)
79         {
80             node[i].l = l[i].k*L + l[i].b;
81             node[i].r = l[i].k*R + l[i].b;
82         }
83         sort(node+1, node+1+n, cmp1);
84         for(int i = 1; i <= n; i++) node[i].id = i;
85         
86         sort(node+1, node+1+n, cmp2);
87         int ans = 0;
88         build(1, n, 1);
89         for(int i = 1; i <= n; i++)
90         {
91             update(node[i].id, 1, 1, n, 1);
92             ans += i - query(1, node[i].id, 1, n, 1);
93         }
94         printf("%d
", ans);
95         
96     }
97     return 0;
98 }