卿学姐与城堡的墙

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

卿学姐终于来到了魔王的城堡，城堡修建的十分壮观。

即使心中放不下公主，卿学姐还是忍不住驻足观赏这宏伟的建筑。

卿学姐注意到城堡的墙上有若干直线状的花纹。

可以将墙看做一个平面，卿学姐想知道有多少种方式任取两个直线，使得这两个直线的交点的横坐标xx满足：u≤x≤vu≤x≤v。

Input

第一行三个整数N,u,vN,u,v，标明直线有NN条。

接下来有NN行，每行两个整数k,bk,b，表示这条直线是y=kx+by=kx+b

1≤N≤2000001≤N≤200000

0≤|k|≤10000000000≤|k|≤1000000000

0≤|b|≤10000000000≤|b|≤1000000000

0≤|u|≤10000000000≤|u|≤1000000000

0≤|v|≤10000000000≤|v|≤1000000000

输入保证u≤vu≤v，保证没有两条直线是一样的

Output

输出一个整数，代表选择的方法数。

Sample input and output

Hint

E - 卿学姐与城堡的墙(树状数组求逆序数)-LMLPHP

上图是样例的解释，交点是A,B,C

其实就是求逆序对数，先分别算出与u的交点和与v的交点，把u从小到大排序，然后依次把与v的交点加入树状数组，因为后加入的直线与u的交点肯定大于先加入直线与u的交点，所以后加入的直线与v的交点只要小于或者等于先加入的直线与v的交点就可以判断出必定相交，也就成了求逆序对数的问题了，还要离散化，因为数据范围都太大了。。。

#pragma GCC diagnostic error "-std=c++11"

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

using namespace std;

typedef long long LL;

const int N =  + ;

struct Point{

    LL x, y;

    bool operator < (const Point &X) const{

        if(x != X.x) return x < X.x;

        return y > X.y;

    }

};

int c[N << ];

vector<Point> a;

vector<LL> tot;

LL Query(int x){

    LL ret = ;

    while(x){

        ret += c[x];

        x -= x&(-x);

    }

    return ret;

}

void change(int x){

    while(x <= (int)tot.size()){

        c[x]++;

        x += x&(-x);

    }

}

int main(){

    //std::ios::sync_with_stdio(false);

    LL n, u, v, b, k;

    cin >> n >> u >> v;

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

        cin >> k >> b ;

        a.push_back((Point){k*u+b, k*v+b});

        tot.push_back(a[i].x);

        tot.push_back(a[i].y);

    }

    sort(tot.begin(), tot.end());

    tot.resize(distance(tot.begin(), unique(tot.begin(), tot.end())));

    for(Point &i:a){

        i.y = (LL)(lower_bound(tot.begin(), tot.end(), i.y) - tot.begin()) + ;

        i.x = (LL)(lower_bound(tot.begin(), tot.end(), i.x) - tot.begin()) + ;

    }

    sort(a.begin(), a.end());

    LL ans = ;

    for(Point &i:a){

        ans += Query((int)tot.size()) - Query(i.y - );

        change(i.y);

    }

    cout << ans << endl;

}