比赛 20120416 评测结果 AAAAAWWWTT
题目名称 牛类刺绣 最终得分 50
用户昵称 王者自由 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-04-16 09:52:00
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 50000 + 10;
struct line {
    int a, b, c;
} l[N];
int n, d, m, x, y, z, s;
bool online(int a, int b, int c) {
    return c*c <= d*d * (a*a + b*b); // |ax+by+c| / sqrt(a^2+b^2) <= d
}
bool cross(int u, int v) {
    if(u >= v) return false;
    x = l[v].c*l[u].b - l[u].c*l[v].b; // x = (c2b1-c1b2)/z
    y = l[v].c*l[u].a - l[u].c*l[v].a; // y = -(c2a1-c1a2)/z
    z = l[u].a*l[v].b - l[v].a*l[u].b; // z = a1b2-a2b1
    return x*x + y*y <= d*d * z*z; // x^2+y^2<=d^2
}
int main() {
    freopen("cowemb.in", "r", stdin);
    freopen("cowemb.out", "w", stdout);
    scanf("%d %d", &n, &d);
    for(int i=0; i<n; i++) {
        scanf("%d %d %d", &x, &y, &z);
        if(online(x, y, z))
            l[m].a = x, l[m].b = y, l[m].c = z, m++;
    }
    for(int i=0; i<m; i++)
        for(int j=i; j<m; j++)
            if(cross(i, j))
                s++;
    printf("%d\n", s);
    return 0;
}