假几何真逆序数 NB HDU3465

题意：

有n条直线，问他们两两在横坐标开区间（L，R）之间相交的个数

n=50000，暴力肯定就不用想了，如果在纸上画一画可以发现如果两条直线在（L，R）内相交，那么他们与x= L和x=R的交点序数是相反的

所以我们只需要算与x=L的交点，然后根据这些点排序编个号，在与R相交，根据新的交点排个逆序，根据编号求逆序数即可。

需要注意的一点:两种特殊情况如果不与L，R相交，那么如果再这个区间内，必定所有直线都会与之相交，记录下数量。

另一种情况就是，如果两个直线的交点正巧在x=L和x=R时，这种情况是不能记录在内的，那么在之前排序的时候与L相交的交点按升序排列

如果交点坐标相同按R交点坐标升序，再根据R的坐标排降序的时候，如果R坐标相同，根据L的坐标排降序，就可以避免这种情况计算在内了。

求逆序数的时候是不会计算在里面的。

求逆序数树状数组即可。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <queue>

 #include <vector>

 #include <algorithm>

 #include <stack>

 #include <set>

 #include <map>

 #include <cmath>

 #define pb push_back

 #define CLR(a) memset(a, 0, sizeof(a));

 #define MEM(a, b) memset(a, b, sizeof(a));

 #define fi first

 #define se second

 using namespace std;

 typedef long long ll;

 const int MAXN = ;

 const int MAXV = ;

 const int MAXE = ;

 const int INF = 0x3f3f3f3f;

 int n;

 struct Node

 {

     double a, b;

     int nu;

     Node () {}

     Node (double a, double b) : a(a), b(b) {}

 }node[MAXN];

 double L, R;

 bool cmpl(Node n1, Node n2)

 {

     if (n1.a == n2.a)

         return n1.b < n2.b;

     else return n1.a < n2.a;

 }

 bool cmpr(Node n1, Node n2)

 {

     if (n1.b == n2.b)

         return n1.a > n2.a;

     else return n1.b > n2.b;

 }

 int cnt = ;

 int c[MAXN << ];

 int lowbit(int x)

 {

     return x&(-x);

 }

 void modify(int x, int data)

 {

     for (int i = x; i < MAXN; i+= lowbit(i))

         c[i] += data;

 }

 int getsum(int x)

 {

     int res = ;

     for (int i = x; i > ; i -= lowbit(i))

         res += c[i];

     return res;

 }

 int main()

 {

     while (~scanf("%d", &n))

     {

         CLR(node);

         CLR(c);

         scanf("%lf%lf", &L, &R);

         cnt = ;

         int vrtcl = ;

         for (int i = ; i < n; i++)

         {

             double x1, y1, x2, y2;

             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

             if (x1 == x2)

             {

                 if (x1 > L && x1 < R) vrtcl++;

                 continue;

             }

             double k = (y2-y1)/(x2-x1);

             double b = y2 - k*x2;

             double l = k*L+b, r = k*R+b;

             node[cnt++] = Node(l, r);

         }

         sort(node, node+cnt, cmpl);

         for (int i = ; i < cnt; i++) node[i].nu = i+;

         sort(node, node+cnt, cmpr);

         //for (int i = 0; i < cnt; i++) cout << node[i].nu << endl;

         int ans = ;

         for (int i = ; i < cnt; i++)

         {

             ans += getsum(node[i].nu);

             modify(node[i].nu, );

         }

         ans += cnt*vrtcl;

         cout << ans << endl;

     }

     return ;

 }

巴特西

假几何真逆序数 NB HDU3465

最新文章

热门文章