kmjp's blog

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

AtCoder Beginner Contest 478 : G - Division Point Hull

なるほど。
https://atcoder.jp/contests/abc478/tasks/abc478_g

問題

N個の点P[i]と、整数p,qが与えられる。
Q(i,j)を、i<jかつP[i]とP[j]をp:qで内分した点とする。

Q(i,j)の凸包の面積を求めよ。

解法

分割統治で解く。
Pを2つに分けたとき問題の凸包は以下の図形の凸包となる。

  • Pの前半分の内分点からなる凸包
  • Pの後半分の内分点からなる凸包
  • Pの前半分からなる凸包と、Pの後ろ半分からなる凸包をq:pでミンコフスキー和を取った図形の凸包
int N,p,q;
ll X[101010],Y[101010];

const ll EPS=0;
template<class C> C veccross(pair<C,C> p1,pair<C,C> p2,pair<C,C> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

template<class C> vector< pair<C, C> > convex_hull(vector< pair<C, C> >& vp) {
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	vector< pair<C, C> > R;
	if(vp.size()<=2) {
		if(vp.size()>=1) R.push_back(vp[0]);
		if(vp.size()>=2 && vp[0]!=vp[1]) R.push_back(vp[1]);
		return R;
	}
	
	FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i));
	sort(sorted.begin(),sorted.end());
	
	res.resize(vp.size()*2);
	/* bottom */
	FOR(i,vp.size()) {
		while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	/* top */
	for(rb=k, i=vp.size()-2;i>=0;i--) {
		while(k>rb && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k-1);
	FORR(v,res) R.push_back(vp[v]);
	
	return R;
}

bool comp(pair<ll,ll> &L,pair<ll,ll> &R) {
	if(L==R) return 0;
	if(L.second==0 && L.first>0) return 1;
	if(R.second==0 && R.first>0) return 0;
	if(L.second>0 && R.second<=0) return 1;
	if(R.second>0 && L.second<=0) return 0;
	if(L.second>=0 && R.second<0) return 1;
	if(R.second>=0 && L.second<0) return 0;
	return L.first*R.second-L.second*R.first>0;
}

//反時計回りに直す
vector<pair<ll,ll>> unticlockwise(vector<pair<ll,ll>> V) {
	ll ret=0;
	int i;
	FOR(i,V.size()) ret+=V[i].first*V[(i+1)%V.size()].second-V[i].second*V[(i+1)%V.size()].first;
	if(ret<0) reverse(ALL(V));
	
	//さらに左下スタートに直す
	int tar=0;
	FOR(i,V.size()) {
		if(V[i].second<V[tar].second) tar=i;
		else if(V[i].second==V[tar].second&&V[i].first<V[tar].first) tar=i;
	}
	rotate(V.begin(),V.begin()+tar,V.end());
	
	return V;
}

vector<pair<ll,ll>> Minkowski_sum(vector<pair<ll,ll>> L,vector<pair<ll,ll>> R) {
	vector<pair<ll,ll>> V;
	int i,tar=0;
	L=unticlockwise(L);
	R=unticlockwise(R);
	
	FOR(i,L.size()-1) V.push_back({L[i+1].first-L[i].first,L[i+1].second-L[i].second});
	V.push_back({L[0].first-L.back().first,L[0].second-L.back().second});
	FOR(i,R.size()-1) V.push_back({R[i+1].first-R[i].first,R[i+1].second-R[i].second});
	V.push_back({R[0].first-R.back().first,R[0].second-R.back().second});
	vector<pair<ll,ll>> P={{L[0].first+R[0].first,L[0].second+R[0].second}};
	sort(ALL(V),comp);
	FORR2(dx,dy,V) {
		P.push_back({P.back().first+dx,P.back().second+dy});
	}
	return P;
}


vector<pair<ll,ll>> dfs(int L,int R) {
	if(L+1==R) {
		return {};
	}
	
	int M=(L+R)/2;
	auto Q1=dfs(L,M);
	auto Q2=dfs(M,R);
	vector<pair<ll,ll>> P1,P2;
	int i;
	for(i=L;i<M;i++) P1.push_back({X[i]*q,Y[i]*q});
	for(i=M;i<R;i++) P2.push_back({X[i]*p,Y[i]*p});
	
	auto Q=Minkowski_sum(convex_hull(P1),convex_hull(P2));
	FORR(a,Q1) Q.push_back(a);
	FORR(a,Q2) Q.push_back(a);
	
	
	
	return convex_hull(Q);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	cin>>N>>p>>q;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
	}
	auto Q=dfs(0,N);
	Q.push_back(Q[0]);
	ll ret=0;
	FOR(i,Q.size()-1) {
		ret+=Q[i].first*Q[i+1].second-Q[i+1].first*Q[i].second;
	}
	ret=abs(ret);
	ll D=2*(p+q)*(p+q);
	ll g=__gcd(ret,D);
	cout<<ret/g<<" "<<D/g<<endl;
	
}

まとめ

この機会に、2つの凸図形のミンコフスキー和を求めるコードもライブラリ化しておいた。