OUPC2012 問題B Closest Segment Pair (AOJ 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; }