Wuyanru's blog
0%

[ABC263Ex] Intersection 2

发表于 分类于 ，

一道看起来难，但是知道算法后让你称妙的题。

打的时候还会发现很难打......

题目链接。

题意

现在平面上有 条直线，每条直线方程为 。

不存在互相平行的直线。

相交的直线会有交点，他们一共会形成 个交点；假如多个直线交于一点，交点要当成多个计算。

求这些交点中，和原点第 近的那个点，到原点的距离。

时限 。

题解

显然，这题我们不能直接暴力计算原点坐标。

考虑进行二分答案。

现在我们的目标就变成了：给出一个圆心为原点的圆，求圆内有多少个交点。

首先，我们可以只看某条直线在圆内的部分，这明显是一条线段。

而且我们可以比较轻松地求出这条线段端点的坐标，具体求法看这里。

然后，我们可以通过反三角函数，求出这些端点对于圆的方位角。

这样子，我们就可以知道端点之间的相对位置。

那么如果两条线段相交了，它们就会满足类似这样的关系：。

直接树状数组算就可以了。

没错，这题的算法就是这么简单。

但是它在Atocder的评分高达 ，当场也只有 位大佬场切。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
using ld=long double;
using ll=long long;
const ld PI=acos(-1);
const ld eps=1e-8;
inline int lowbit(int i){ return i&(-i);}
struct node
{
    int l,r;
}seg[50001];
bool vis[50001];
ld num[100001];
ld lth[50001];
ld rth[50001];
int t[100001];
int A[50001];
int B[50001];
int C[50001];
int tot;
int n;
ll k;
ld get_theta(ld x,ld y)
{
    if(abs(x)<=eps)
    {
        if(y>=0) return PI/2;
        return PI*3/2;
    }
    ld k=y/x;
    if(y<0) k=-k;
    if(x<0) k=-k;
    ld ans=atan(k);
    if(x<0) ans=PI-ans;
    if(y<0) ans=2*PI-ans;
    // printf("%.6Lf %.6Lf : %.6Lf %.6Lf %.6Lf\n",x,y,k,ans,ans/PI*180);
    return ans;
}
void add(int x)
{
    while(x<=tot)
    {
        t[x]++;
        x+=lowbit(x);
    }
}
int get(int x)
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
bool cal(ld r)
{
    // printf("r=%.8Lf\n",r);
    tot=0;
    for(int i=1;i<=n;i++)
    {
        vis[i]=1;
        if(B[i]==0)
        {
            ld x=-ld(C[i])/A[i];
            if(x>r) vis[i]=0;
            else if(abs(x-r)<=eps) 
            {
                ld y=0;
                lth[i]=rth[i]=get_theta(x,y);
                num[++tot]=lth[i];
            }
            else
            {
                ld y1=sqrtl(r*r-x*x);
                ld y2=-y1;
                // printf("%6Lf %6Lf ",x,y1);
                // printf("%6Lf %6Lf\n",x,y2);
                lth[i]=get_theta(x,y1);
                rth[i]=get_theta(x,y2);
                if(lth[i]>rth[i]) swap(lth[i],rth[i]);
                num[++tot]=lth[i];
                num[++tot]=rth[i];
            }
            continue;
        }
        ld a=A[i]*A[i]+B[i]*B[i];
        ld b=2*A[i]*C[i];
        ld c=C[i]*C[i]-r*r*B[i]*B[i];
        ld delta=b*b-4*a*c;
        if(delta<-eps) vis[i]=0;
        else if(abs(delta)<=eps)
        {
            ld x=-b/a/2;
            ld y=-(A[i]*x+C[i])/B[i];
            lth[i]=rth[i]=get_theta(x,y);
            num[++tot]=lth[i];
        }
        else
        {
            ld x1=(-b+sqrtl(delta))/a/2;
            ld y1=-(A[i]*x1+C[i])/B[i];
            ld x2=(-b-sqrtl(delta))/a/2;
            ld y2=-(A[i]*x2+C[i])/B[i];
            // printf("%6Lf %6Lf ",x1,y1);
            // printf("%6Lf %6Lf\n",x2,y2);
            lth[i]=get_theta(x1,y1);
            rth[i]=get_theta(x2,y2);
            if(lth[i]>rth[i]) swap(lth[i],rth[i]);
            num[++tot]=lth[i];
            num[++tot]=rth[i];
        }
    }
    sort(num+1,num+tot+1);
    int len=unique(num+1,num+tot+1)-num-1,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]) continue;
        cnt++;
        seg[cnt].l=lower_bound(num+1,num+len+1,lth[i])-num;
        seg[cnt].r=lower_bound(num+1,num+len+1,rth[i])-num;
        // printf("%d %d\n",seg[cnt].l,seg[cnt].r);
    }
    sort(seg+1,seg+cnt+1,[](node a,node b){return a.l<b.l;});
    ll ans=0;
    for(int i=1;i<=tot;i++) t[i]=0;
    for(int i=1;i<=cnt;i++)
    {
        ans+=get(seg[i].r)-get(seg[i].l-1);
        add(seg[i].r);
    }
    return ans>=k;
}
int main()
{
    // freopen("data.out","w",stdout);
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d%d%d",A+i,B+i,C+i);
    ld ans=0;
    for(ld i=2097152;i>=eps;i/=2) if(!cal(ans+i)) ans+=i;
    printf("%.8Lf\n",ans);
    return 0;
}

这个代码是真难打。

我数学贼烂，解析几何和三角函数都不会......

所以代码打得又臭又长。

感谢观看！