本番中に間に合わず。
https://atcoder.jp/contests/abc263/tasks/abc263_h
問題
2次元座標中に、互いに平行でない直線がN個与えられる。
個々には、重複を含めると2直線の交点がN*(N-1)/2個存在する。
このうち、原点からの距離が近い順にK個目の交点について、原点からの距離を求めよ。
解法
原点から距離R内に、何個交点があるかを高速に求められれば、二分探索でRを求められる。
各直線のうち、原点から距離Rの円と交差するものがある場合、その交点の偏角を求めよう。
2つの直線A,Bにおいて、上記交点の偏角をA1,A2,B1,B2とする。
これらの昇順の並びが(A1,B1,A2,B2)または(B1,A1,B2,A2)となる場合、両直線の交点は距離R内にあることになる。
このような関係をO(NlogN)で列挙しよう。
偏角をソートし、また各直線の偏角の差が短い順に、BITを使って両偏角の間にある他頂点の偏角の個数を求めればよい。
ll N; ll K; ll A[50505],B[50505],C[50505]; int L[202020],R[202020]; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<int,17> bt; ll hoge(double v) { vector<pair<double,int>> V; int i; FOR(i,N) { L[i]=R[i]=-1; double r=hypot(A[i],B[i]); double d=abs(C[i])/r; double D=(A[i]*A[i]+B[i]*B[i])*v*v-C[i]*C[i]; if(D<=1e-8) continue; D=sqrt(D); double x1=(-A[i]*C[i]+B[i]*D)/(A[i]*A[i]+B[i]*B[i]); double y1=(-B[i]*C[i]-A[i]*D)/(A[i]*A[i]+B[i]*B[i]); double x2=(-A[i]*C[i]-B[i]*D)/(A[i]*A[i]+B[i]*B[i]); double y2=(-B[i]*C[i]+A[i]*D)/(A[i]*A[i]+B[i]*B[i]); V.push_back({atan2(y1,x1),i}); V.push_back({atan2(y2,x2),i}); } sort(ALL(V)); ZERO(bt.bit); vector<pair<int,int>> len; FOR(i,V.size()) { bt.add(i,1); if(L[V[i].second]==-1) { L[V[i].second]=i; } else { R[V[i].second]=i; len.push_back({i-L[V[i].second],V[i].second}); } } sort(ALL(len)); ll sum=0; FORR2(a,x,len) { sum+=bt(R[x]-1)-bt(L[x]); bt.add(L[x],-1); bt.add(R[x],-1); } return sum; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) cin>>A[i]>>B[i]>>C[i]; double L=0,R=1e9; FOR(i,60) { double M=(L+R)/2; if(hoge(M)<K) L=M; else R=M; } _P("%.12lf\n",L); }
まとめ
これは自力で思いつけて良かったな。
精度が心配だったけど、どうにか通った。