题解：P2950 [USACO09OPEN] Bovine Embroidery G

· · 题解

我是 50 号，喜欢 29 号，所以一定要做 P2950。

题意：给定一个以原点为圆心且半径为 d 的圆还有 N 条直线，求有多少对直线的交点在圆内或圆上。

分析两条直线相交于圆内或圆上的条件。考虑取它们和圆的四个交点，如图（图片来源 @fy0123）。\ \ 可以发现，当且仅当交点交叉排列，直线交于圆内或圆上（若交于圆上，则交点重合，也可以通过交换重合点构造出交叉排列）。

断环成链，不妨将点转化为它与原点连线的倾斜角，直线转化为倾斜角的闭区间，相交于圆内或圆上当且仅当：两个区间不真包含且有交。

然后就做完了，变成了二维偏序。具体地，将区间按左端点排序，从左到右将右端点放入树状数组，查询区间内包含多少个右端点即可。

AC 代码。

#include <bits/stdc++.h>
#define fi first
#define se second
#define mid ((l+r)>>1)
#define bmid ((l+r+1)>>1)
#define pb push_back
#define eb emplace_back
using namespace std;
using ll= long long;
#ifndef ONLINE_JUDGE
template <typename tp>
void _debug(const tp& t) {cerr<<t<<'\n';}
template <typename tp,typename... args>
void _debug(const tp& t, const args&... rest) {cerr<<t<<' ';_debug(rest...);}
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)
#else
#define debug(...) 0
#endif
#define int ll
#define eps 1e-9
const int N=100005,H=N<<2,inf=1000000000,mod=1000000007;
int n,d;
pair<double,double> hht(int a,int b,double c) {
    if(a<0) a*=-1,b*=-1,c*=-1;
    int dlt=b*b-4*a*c;
    if(dlt<0) return make_pair(1,0);
    return make_pair((-b-sqrt(dlt))/(a<<1),(-b+sqrt(dlt))/(a<<1));
}
pair<double,double> llq(int a,int b,double c){
    double x1,y1,x2,y2;
    if(!a) {
        y1=y2=-c/b;
        if(y1<-d-eps||y1>d+eps) return make_pair(1,0);
        x1=sqrt(d*d-y1*y1);
        x2=-x1;
    } else {
        auto t=hht(a*a+b*b,2*b*c,c*c-double(a*a)*d*d);
        y1=t.fi,y2=t.se;
        if(y1>y2) return make_pair(1,0);
        x1=-(b*y1+c)/a,x2=-(b*y2+c)/a;
    }
    double ret1=atan2(x1,y1),ret2=atan2(x2,y2);
    if(ret1<ret2-eps) return make_pair(ret1,ret2);
    else return make_pair(ret2,ret1);
}
vector<pair<double,int> > vec;
int V,c[N];
void add(int i,int x) {
    for(;i<=V;i+=i&-i)
        c[i]+=x;
}
int query(int i) {
    int ret=0;
    for(;i;i-=i&-i)
        ret+=c[i];
    return ret;
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>d;
    for(int a,b,c,i=1;i<=n;i++) {
        cin>>a>>b>>c;
        if(abs(c)>d*sqrt(a*a+b*b)) {n--,i--;continue;}
        auto t=llq(a,b,c);
        vec.eb(t.fi,i),vec.eb(t.se,i);
    }
    sort(vec.begin(),vec.end());
    vector<vector<int> > ran(n+1);
    for(int p=0;p<vec.size();) {
        V++;
        do ran[vec[p++].se].pb(V);
        while(p<vec.size()&&fabs(vec[p].fi-vec[p-1].fi)<eps);
    }
    for(int i=1;i<=n;i++) {
        sort(ran[i].begin(),ran[i].end());
    }
    sort(ran.begin()+1,ran.begin()+n+1,[](auto x,auto y) {
        return x[0]!=y[0]?x[0]<y[0]:x[1]<y[1];
    });
    int ans=0;
    for(int i=1;i<=n;i++) {
        debug(ran[i][0],ran[i][1]);
        ans+=query(ran[i][1])-query(ran[i][0]-1);
        add(ran[i][1],+1);
    }
    cout<<ans;
    return 0;
}