OUPC2012 問題B Closest Segment Pair (AOJ 2351)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2351）

制約条件

入力は全て整数
n≦10^5
0≦xi,yi≦100

方針

nが大きいのでn^2回計算するのは無理。
(x,y)の取りうる値が1万通りしかないので、線分が5000本より多くあれば必ずどれかが1点を共有することになることに注目する。

すなわち、n≧5001のときは即座に0を返せばいい。

それ以下のときは全部調べる、のだが愚直に全部調べるとTLE.
線分をx座標の順にソートしておいて、x座標が今までの最適解より大きかったら枝刈りすると、結構速くなって通る。

ソースコード

//幾何のコードは省略（spaghetti source）
struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
	bool operator<(const L &o)const{
		return (*this)[0].real()<o[0].real();
	}
};
int main(){
	int n; cin>>n;
	if(n>5100){
		cout<<0<<endl; return 0;
	}
	vector<L> ls;
	rep(i,n){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		if(x1<x2)ls.pb(L(P(x1,y1),P(x2,y2)));
		else ls.pb(L(P(x2,y2),P(x1,y1)));
	}
	sort(all(ls));
	
	double ans=INF;
	rep(i,n)for(int j=i+1;j<n;j++){
		if(ls[j][0].real()-ls[i][1].real()>=ans)break;
		ans=min(ans,distanceSS(ls[i],ls[j]));
	}
	printf("%.9f\n",ans);
	return 0;
}