TopCoder SRM 801 : Div1 Hard PolylineCover

うーん、時間が足りず。
https://community.topcoder.com/stat?c=problem_statement&pm=16826&rd=18530

問題

N個のPolylineが与えられる。
いずれも長さは200,000以下である。

ある単一の矩形を用いて、それぞれのPolylineを覆いたい。
Polylineごとに、矩形は回転・平行移動して覆ってもよい。

矩形の条件として下記を満たすものとする。

• 面積は2*10^10以下
• 短辺の長さは100以上

各Polylineを覆う単一の矩形とその位置を定めよ。

解法

Polylineの長さが長いときは上限200,000だし、Polylineの張る最大の矩形の面積は100,000*100,000=10^10となりそうである。
そこで、面積を見ると、100,000*200,000の矩形を準備すればいずれの場合もカバーできそうである。

そこで各Polylineについて、最遠点対を求めよう。
矩形の長辺の向きを、その2点の向きに合わせる。
あとはPolylineの全点を覆えるよう短辺に位置を合わせよう。

Polylineが同じ頂点を複数持つ場合に注意。

class PolylineCover {
	public:
	vector<double> hoge(vector<pair<int,int>> V) {
		sort(ALL(V));
		unique(ALL(V));
		V.erase(unique(ALL(V)),V.end());
		
		if(V.size()==1) {
			auto p=*V.begin();
			return {p.first-100000.0,p.second+50000.0,p.first+100000.0,p.second+50000.0,p.first+100000.0,p.second-50000.0};
		}
		
		int N=V.size();
		pair<ll,ll> S,T;
		double mad=-1;
		int a,b;
		FORR(a,V) FORR(b,V) if(a<b) {
			double dx=b.first-a.first;
			double dy=b.second-a.second;
			double d=hypot(dx,dy);
			if(d>mad) {
				S=a;
				T=b;
				mad=d;
			}
		}
		
		double dx=(T.first-S.first)/mad;
		double dy=(T.second-S.second)/mad;
		double ex=dy;
		double ey=-dx;
		double ma=0,mi=0;
		FORR(c,V) {
			double fx=c.first-S.first;
			double fy=c.second-S.second;
			double cr=fx*ex+fy*ey;
			ma=max(ma,cr);
			mi=min(mi,cr);
		}
		ma=mi+100000;
		vector<double> ret;
		ret.push_back(S.first+mi*ex);
		ret.push_back(S.second+mi*ey);
		ret.push_back(S.first+200000*dx+mi*ex);
		ret.push_back(S.second+200000*dy+mi*ey);
		ret.push_back(S.first+200000*dx+ma*ex);
		ret.push_back(S.second+200000*dy+ma*ey);
		return ret;
	}
	
	
	vector <double> cover(vector <int> L, vector <int> X, vector <int> Y) {
		int cur=0;
		vector <double> ret;
		FORR(v,L) {
			vector<pair<int,int>> V;
			int i;
			FOR(i,v) {
				V.push_back({X[cur],Y[cur]});
				cur++;
			}
			auto r=hoge(V);
			FORR(a,r) ret.push_back(a);
		}
		return ret;
		
	}
}

まとめ

うーん、解けてもあんまりうれしくないHard。