E - 卿学姐与城堡的墙

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

Submit  Status

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

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

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

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

Input

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

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

$1\le N \le 200000$

$0\le \left | k \right | \le 1000000000$

$0\le \left |b \right | \le 1000000000$

$0\le \left |u \right | \le 1000000000$

$0\le \left |v \right | \le 1000000000$

输入保证$u \le v$，保证没有两条直线是一样的

Output

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

Sample input and output

Sample Input Sample Output 3 -3 1 -1 3 2 2 1 1 3

Hint

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

题解：在两条直线x=u和x=v之间有交点可以等同于f(u)<g(u)&f(v)>g(v),因此这个问题就转化为了一个逆序对问题，只要求出逆序对数量即可

代码：

#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> using namespace std; typedef struct num { long long k1; long long b1; long long y1; bool operator <(const num &other)const { if(y1==other.y1) return k1>other.k1; else return y1<other.y1; } }Num1; Num1 lin[400000]; long long t[400000]; long long sum=0; void merge(long long* a,long long l, long long mid, long long r ) { long long p = 0; long long i = l, j = mid + 1; while(i <= mid&& j <= r) { if(a[i] >= a[j]) { t[p++] = a[j++]; sum =sum + mid - i + 1; } else { t[p++] = a[i++]; } } while(i <= mid) t[p++] = a[i++]; while(j <= r) t[p++] = a[j++]; for(i = 0; i < p; i++) { a[l + i] = t[i]; } } void mergesort(long long*a,long long l ,long long r) { if(l < r) { long long mid = (r - l) / 2 + l; mergesort(a,l , mid); mergesort(a,mid + 1 , r); merge(a,l, mid , r); } } int main() { long long N,u,v; long long y2[200001]; scanf("%lld %lld %lld",&N,&u,&v); for(long long i=0;i<N;i++) { scanf("%lld %lld",&lin[i].k1,&lin[i].b1); lin[i].y1=lin[i].k1*u+lin[i].b1; } sort(&lin[0],&lin[N]); for(long long i = 0;i<N;i++) { y2[i]=lin[i].k1*v+lin[i].b1; } mergesort(y2,0,N-1); printf("%lld",sum); return 0; }