LeetCode Weekly Contest 427 : 3382. Maximum Area Rectangle With Point Constraints II

割とめんどい。
https://leetcode.com/problems/maximum-area-rectangle-with-point-constraints-ii/description/

問題

二次元座標上でN点の位置が与えられる。
以下を満たす長方形の面積の最大値を求めよ。

• 軸に平行で面積が正の長方形である。
• 各点は、N点のうち4点の座標と一致する。
• 長方形の内部や外周部に、四隅の点以外の点が含まれない。

解法

点のY座標の大きい順に、点を加えて行く。
その際、追加済みの点に対し、以下を持とう。

• X座標毎に、点が存在するY座標の最小値
• 座標圧縮したX座標毎に、点が存在するY座標の最小値をSegTreeで持つ
• Y座標毎に、点が存在するX座標の最小値
• 点の位置の集合

点を追加する際、その点が左下の点となるケースを考える。
同じX座標・Y座標の点を探せば、四隅の点のうち3点が確定する。残り1点の座標にも、追加済みの点があるか判定すれば四隅の点が確定する。
あとは四隅の点以外に、長方形内に点がないか判定すればよい。
これは、Segtreeで指定のX座標の範囲内に、長方形の上端より低い位置に点がないかチェックすればよい。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;

class Solution {
public:
    long long maxRectangleArea(vector<int>& xCoord, vector<int>& yCoord) {
		map<int,vector<int>> XminY;
		map<int,int> YminX;
		set<pair<int,int>> S;
		vector<pair<int,int>> cand;
		vector<int> Xs=xCoord;
		int N=xCoord.size();
		sort(ALL(Xs));
		Xs.erase(unique(ALL(Xs)),Xs.end());
		int i;
		
		FOR(i,N) {
			st.update(i,1<<30);
			cand.push_back({yCoord[i],xCoord[i]});
		}
		sort(ALL(cand));
		reverse(ALL(cand));
		ll ret=-1;
		FORR(c,cand) {
			int y=c.first;
			int x=lower_bound(ALL(Xs),c.second)-Xs.begin();
			int ty=-1,tx=-1;
			if(XminY.count(x)) ty=XminY[x].back();
			if(YminX.count(y)) tx=YminX[y];
			if(S.count({tx,ty})&&XminY[tx][XminY[tx].size()-2]==ty) {
				if(st.getval(x+1,tx)>ty) {
					ret=max(ret,1LL*(ty-y)*(Xs[tx]-Xs[x]));
				}
			}
			S.insert({x,y});
			XminY[x].push_back(y);
			YminX[y]=x;
			st.update(x,y);
		}
		return ret;
		
        
    }
};

まとめ

最終的にコード量はそこまで多くないけど、なんか面倒くささを感じる。