Description

Bessie学会了刺绣这种精细的工作。牛们在一片半径为d(1 <= d <= 50000)的圆形布上绣花. 它们一共绣了N (2 <= N <= 50000)条直线，每条直线连接布的边缘上的两个点(没有两条线通过边上同一个点)。 作为一只热爱数学的牛，Bessie 知道每条线的公式, ax + by + c = 0. a, b, 和 c 为整数(-1000000 <= a <= 1000000; -1000000 <= b <= 1000000; -1000000 <= c <= 1000000).没有两条线完全重合。 不幸的是, 一部分线不通过圆布的内部. 原点(0,0)在布的正中央, 所有边上的点离原点距离为d. 每条线的公式满足至少a,b中的一个非零. 对于牛来说，刺绣作品中线的交点越多，便越有价值。帮助Bessie计算在圆中相交的线的对数，也就是说交点与原点的距离小于d。注意如果三条线在圆内同一点相交,这算3对线。4线共点->6对线.

Input

第1行: 两个空格分开的数, N 和 d 第2..N+1行: 第 i+1 行包含第i条线的参数: a, b 和 c

Output

第1行: 一行，包含一个数,为在园内相交的线的对数.

Sample Input

2 1

1 0 0

0 1 0

输入说明：

两条直线x=0和y=0.

Sample Output

1

HINT

两条线在(0,0)相交, 明显离原点距离小于1.

Source

Gold

观察这个题可以发现，两个直线若存在交点并且交点在圆内，那么两个直线所对应于圆上的两条弧(不管是优弧还是劣弧都是一回事)是 相交且不包含的。

Q:为什么不用管弧是优弧还是劣弧呢？
A:因为如果两条和圆相交的直线不存在交点，那么它们分别相对应的优弧或劣弧总会是相离或包含的，不会是相交 的。

那么我们就可以想出这样一个做法：

  1. 我们除去那些和圆不相交的直线，然后把每条直线和圆的两个交点(若相切，就视为两个相同的交点)求出 来，并求出两个交点和圆心连线的极角，标记每个极角所属的直线编号
  2. 然后把所有的极角降序排序，一个 直线就对应于两个极角下标所夹的区间，这样整个圆变成了一个大线段

然后问题变为线段里有若干个区间，问有多少对区间相交且不包含。
暴力做法很好想。
正解：复杂度为(O(nlogn))的做法。
称某条直线与圆的2个交点中，按照极角排序后较小的为左括号，较大的为右括号。设数组C[]，初始化为0。 for i ∈ 所有交点 if i 为某条直线L的左括号 C[i] = 1 else j = i对应的该条直线的左括号 ans += C[j+1]+…+C[i] C[j] = 0
(转自http://www.quartergeek.com/bzoj1573/)
其中C数组的求和和修改过程如果不优化，那么这个做法复杂度就是O(n^2)的了，因此用树状数组或线段树优化这一部分即可。对C数组求和求的就 是在当前区间的左边，且和当前区间相交不包含的区间个数。如果访问到了第i个区间的右端点，那么之后所有的区间都不会和该区间相交，就要在树状数组里 删去这个区间的左端点的权值1了。

#include <bits/stdc++.h>
#define N 100010
#define lowbit(x) ((x)&(-(x)))
#define ll long long 
using namespace std;
int n;
ll d;
struct Point
{
    double ang;
    int x;
    Point(){}
    Point(double _ang,int _bel):ang(_ang),x(_bel){}
}p[N];

bool cmp(Point a,Point b)
{
    return a.ang > b.ang;
}
int tot, bit[N], vis[N];
int query(int x)
{
    int ans = 0;
    while(x)
    {
        ans += bit[x];
        x -= lowbit(x);
    }
    return ans;
}

void update(int x,int addv)
{
    while(x <= 2 * n)
    {
        bit[x] += addv;
        x += lowbit(x);
    }
}

int main()
{
    ll ans = 0;
    scanf("%d%lld",&n,&d);
    for(int i = 1; i <= n; i ++)
    {
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        if(c * c <= d * d * (a * a + b * b))
        {
            if(b != 0)
            {
                double A = (1 + (double)(a * a) / (double)(b * b));
                double B = (double)(2 * a * c) / (double)(b * b);
                double C = (double)(c * c) / (double)(b * b) - (double)(d * d);
                double x1 = (-B + (double)sqrt(B * B - 4 * A * C)) / (2 * A);
                double x2 = (-B - (double)sqrt(B * B - 4 * A * C)) / (2 * A);
                double y1 = -((double)a / (double)b) * x1 - (double)c / (double)b;
                double y2 = -((double)a / (double)b) * x2 - (double)c / (double)b;
                p[++ tot] = Point(atan2(y1,x1),i);
                p[++ tot] = Point(atan2(y2,x2),i);
            }
            else
            {
                double x = -(double)c / (double)a;
                double y1 = sqrt((double)(d * d) - x * x);
                double y2 = -sqrt((double)(d * d) - x * x);
                p[++ tot] = Point(atan2(y1, x), i);
                p[++ tot] = Point(atan2(y2, x), i);
            }
        }
    }
    sort(p + 1, p + tot + 1, cmp);
    for(int i = 1; i <= tot; i ++)
    {
        if(vis[p[i].x])
        {
            ans += query(i) - query(vis[p[i].x]);
            update(vis[p[i].x], -1);
        }
        else
        {
            vis[p[i].x] = i;
            update(i,1);
        }
    }
    printf("%lld\n",ans);
    return 0;
}