AtCoder ABC #251 (パナソニックグループプログラミングコンテスト2022) : G - Intersection of Polygons

しょうもないミスが痛い…。
https://atcoder.jp/contests/abc251/tasks/abc251_g

問題

凸N多角形Pの座標が与えられる。
ここで、加えてM個のベクトルが与えられる。
Pを、それぞれのベクトルに沿って移動させてできるM個の多角形を考える。

その後、Q個のクエリが与えられる。
各クエリでは座標が指定されるので、上記M個の多角形すべての内側にあるか判定せよ。

解法

多角形を反時計回りに辺に沿って考えると、ある点が多角形の内側にあるということは、各辺の左側にあることになる。
よって、元の多角形のN辺に対し、M個のベクトルのうち、「各辺の左側にある」ことが最も厳しくなるようなもの、すなわち元の位置から最も左側に辺を動かすベクトルのみ考えればよい。

あらかじめ各辺を動かして置き、各クエリでは、与えられた座標が(動かした後)の各辺の左側にあるかを改めて判定しよう。

int N,M,Q;
ll X[202020],Y[202020];
ll CX[202020],CY[202020];
ll DX[202020],DY[202020];
ll U,V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,N) {
		DX[i]=X[(i+1)%N]-X[i];
		DY[i]=Y[(i+1)%N]-Y[i];
	}
	
	cin>>M;
	FOR(i,M) {
		cin>>U>>V;
		if(i==0) {
			FOR(j,N) {
				CX[j]=U;
				CY[j]=V;
			}
		}
		else {
			FOR(j,N) {
				if((U-CX[j])*DY[j]-(V-CY[j])*DX[j]<0) {
					CX[j]=U;
					CY[j]=V;
				}
			}
		}
	}
	FOR(i,N) X[i]+=CX[i],Y[i]+=CY[i];
	
	
	cin>>Q;
	while(Q--) {
		ll TX,TY;
		cin>>TX>>TY;
		FOR(i,N) {
			if((TX-X[i])*DY[i]-(TY-Y[i])*DX[i]>0) break;
		}
		if(i==N) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
	
}

まとめ

似たようなのをCodeforcesで見たような気がするけど、あっちは多角形を狭めるほうでなく広げるほうだったかな。