记录编号	424031	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 牛类刺绣	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.146 s
提交时间	2017-07-12 19:46:09	内存使用	9.45 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long double db;
const db eps=1e-9;
const int N=2e5+10;
int n,m,id;
db d,l[N],r[N],a[N];
int rank(db x){
	int l=1,r=m;
	while (l<r){
		int mid=(l+r)>>1;
		if (a[mid+1]<x+eps) l=mid+1;else r=mid;
	}
	return l;
}
typedef pair<int,int> pii;
pii p[N];
struct bit{
	int a[N];
	void add(int p,int d){
		for (;p<N;p+=p&-p) a[p]+=d;
	}
	int sum(int p){
		int ans=0;
		for (;p;p-=p&-p) ans+=a[p];
		return ans;
	}
}T;
int main()
{
	freopen("cowemb.in","r",stdin);
	freopen("cowemb.out","w",stdout);
	scanf("%d%Lf",&n,&d);
	for (int i=1;i<=n;i++){
		db a,b,c;
		scanf("%Lf%Lf%Lf",&a,&b,&c);
		db det=a*a+b*b,Sqrt=det*d*d-c*c;
		if (Sqrt<0) continue;
		Sqrt=b*sqrt(Sqrt);
		db x1=(-a*c+Sqrt)/det,x2=(-a*c-Sqrt)/det;
		db y1=sqrt(d*d-x1*x1),y2=sqrt(d*d-x2*x2);
		if (abs(a*x1+b*y1+c)>eps) y1=-y1;
		if (abs(a*x2+b*y2+c)>eps) y2=-y2;
		if (abs(x1-x2)<eps&&abs(y1-y2)<eps) y1=-y1;
		id++;
		::a[++m]=l[id]=atan2(y1,x1);
		::a[++m]=r[id]=atan2(y2,x2);
	}
	sort(a+1,a+m+1);
	for (int i=1;i<=id;i++){
		p[i]=pii(rank(r[i]),rank(l[i]));
		if (p[i].first<p[i].second) swap(p[i].first,p[i].second);
	}
	sort(p+1,p+id+1);
	long long ans=0;
	for (int i=1;i<=id;i++){
		ans+=T.sum(p[i].second);
		T.add(p[i].second,1);
		T.add(p[i].first+1,-1);
	}
	printf("%lld\n",ans);
	return 0;
}