正題

題目鏈接:https://www.luogu.com.cn/problem/CF1446F

---

題目大意

給出$n$個(gè)點(diǎn)，求所有點(diǎn)對(duì)構(gòu)成的直線中與原點(diǎn)距離第$k$小的距離

$2\le n\le 10^5,1\le k\le \frac{n(n?1)}{2}$

---

解題思路

二分還是挺顯然的，考慮二分了之后怎么判斷一個(gè)距離以內(nèi)的直線數(shù)量

兩個(gè)點(diǎn)對(duì)之間的直線在原點(diǎn)距離$d$以內(nèi)，也就是這條直線經(jīng)過原點(diǎn)為中心半徑為$d$的圓。換一種理解，也就是如果有這個(gè)圓那么這兩個(gè)點(diǎn)對(duì)之間無法相互看見。

現(xiàn)在問題變?yōu)榱饲笥卸嗌賯€(gè)點(diǎn)對(duì)之間無法相互看見，給張官方題解的圖片就挺容易理解的

也就是說我們對(duì)于每個(gè)點(diǎn)找到它與圓的兩個(gè)切點(diǎn)之間在圓上構(gòu)成的一個(gè)區(qū)間。

如果兩個(gè)點(diǎn)的區(qū)間有交集那么他們就可以相互看見。

現(xiàn)在問題就變?yōu)榱饲笥卸嗌賹?duì)區(qū)間有交。

這個(gè)直接用樹狀數(shù)組統(tǒng)計(jì)就好了。

環(huán)的話直接斷開，跨越了環(huán)的就取反。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long #define lowbit(x) (x&-x) using namespace std; const ll N=2e5+10; double eps=1e-8,Pi=acos(-1); ll n,k,cnt,m,t[N],p[N],l[N],r[N]; double a[N],b[N],c[N],L[N],R[N]; bool v[N]; void Change(ll x,ll val){while(x<=cnt){t[x]+=val;x+=lowbit(x);}return; } ll Ask(ll x){ll ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans; } bool cmp(ll x,ll y) {return l[x]<l[y];} ll check(double d){cnt=0;m=0;for(ll i=1;i<=n;i++)v[i]=0;for(ll i=1;i<=n;i++){double dis=sqrt(a[i]*a[i]+b[i]*b[i]);if(dis-d<eps){v[i]=1;continue;}double ang=atan2(b[i],a[i]),ta=acos(d/dis);L[i]=ang-ta;R[i]=ang+ta;if(L[i]<-Pi)L[i]+=2*Pi;if(R[i]>Pi)R[i]-=2*Pi;if(L[i]>R[i])swap(L[i],R[i]);c[++cnt]=L[i];c[++cnt]=R[i]; }sort(c+1,c+1+cnt);for(ll i=1;i<=n;i++){if(v[i])continue;p[++m]=i;l[i]=lower_bound(c+1,c+1+cnt,L[i])-c;r[i]=lower_bound(c+1,c+1+cnt,R[i])-c;}memset(t,0,sizeof(t));sort(p+1,p+1+m,cmp);ll ans=n*(n-1)/2;for(ll i=1;i<=m;i++){ll x=p[i];ans-=Ask(r[x])-Ask(l[x]-1);Change(r[x],1);}return ans; } signed main() {scanf("%lld%lld",&n,&k);for(ll i=1;i<=n;i++)scanf("%lf%lf",&a[i],&b[i]);double l=0,r=20000;while(r-l>=eps){double mid=(l+r)/2.0;if(check(mid)<k)l=mid;else r=mid;}printf("%.10lf",l);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1446F-Line Distance【计算几何,树状数组,二分】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。