题解 | Embroidery-牛客假日团队赛9E题
E-Bovine Embroidery_牛客假日团队赛9
https://ac.nowcoder.com/acm/contest/1071/E
题目描述
Bessie has taken up the detailed art of bovine embroidery. Cows embroider a cloth mounted in a circular hoop of integer radiusBeing mathematically inclined, Bessie knows a formula of the form ax + by + c = 0 for each straight line piece of thread. Conveniently, a, b, and c are integers
Perhaps less conveniently, Bessie knows that her set of formula coefficients also includes a number of formulae for threads that do not appear to pass inside the hoop's circle. She regrets this greatly.
The origin (0,0) is in the precise middle of the hoop, so all points on the hoop's edge are distance d from the origin. At least one of the coefficients a and b is non-zero for each thread's formula.
Bovine embroidery is more highly regarded when the number of thread intersections is maximized. Help Bessie: count the number of pairs of threads that intersect on the cloth (i.e., within distance d of the origin). Note that if three threads happen to coincide at the same point, that would be three pairs of intersections. Four threads at the same point -> six pairs of intersections, etc.
输入描述:
* Line 1: Two space-separated integers: N and d
* Lines 2..N+1: Line i+1 describes thread i with three integers: a, b, and c
输出描述:
* Line 1: One integer, on a line by itself, that is the count of pairs of threads that intersect.
示例1
输入
2 1
1 0 0
0 1 0
输出
1
说明
The two lines are x=0 and y=0.
The two lines intersect at (0,0), which is clearly with 1 of the origin.
解答
The two lines are x=0 and y=0.
The two lines intersect at (0,0), which is clearly with 1 of the origin.
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 100010
int n,num,c[N],vis[N];
long long ans,d;
const double eps=1e-9;
struct node{
double ct;
int id;
}p[N];
bool cmp(node x,node y){
return x.ct-y.ct>eps;
}
int lowbit(int x){return x&(-x);}
void update(int p,int x){
while(p<=2*n){
c[p]+=x;
p+=lowbit(p);
}
}
long long query(int p){
long long sum=0;
while(p){
sum+=c[p];
p-=lowbit(p);
}
return sum;
}
int main(){
//freopen("Cola.txt","r",stdin);
scanf("%d%lld",&n,&d);
long long a,b,c;
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&a,&b,&c);
//cin>>a>>b>>c;
if(c*c<d*d*(a*a+b*b)){
double tmp=a*a+b*b,tmp2=sqrt(d*d*tmp-c*c);
double x1=(a*c+b*tmp2)/tmp;
double x2=(a*c-b*tmp2)/tmp;
double y1=(b*c-a*tmp2)/tmp;
double y2=(b*c+a*tmp2)/tmp;
p[++num].ct=atan2(y1,x1);p[num].id=i;
p[++num].ct=atan2(y2,x2);p[num].id=i;
}
}
sort(p+1,p+1+num,cmp);
for(int i=1;i<=num;i++){
if(vis[p[i].id]){
ans+=query(i)-query(vis[p[i].id]);
update(vis[p[i].id],-1);
}
else {
vis[p[i].id]=i;
update(i,1);
}
}
printf("%lld",ans);
return 0;
} 来源：Soda
