kmjp's blog

競技プログラミング参加記です

AtCoder ABC #263 (LINE Verda プログラミングコンテスト) : Ex - Intersection 2

本番中に間に合わず。
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);
	
}

まとめ

これは自力で思いつけて良かったな。
精度が心配だったけど、どうにか通った。