topcoder

kojingharangの日記

2012-03-25

Codeforces 166B Polygons

10:27 |

A ポリゴンは convex, B ポリゴンはそうとは限らない。B が A の中にあるかどうかを求める問題。
A, Bの頂点数を N, M として N <= 10^5, M <= 2*10^4

B ポリゴンは単なる点の集合だと思って、X でソートしておく。
まず A の X 座標の範囲から外れる B の点があったら NG
A ポリゴンの各辺 e について、その辺の X の範囲にある B ポリゴンの点集合を２分探索で求めて...
e が +X 方向なら辺の下(-Y方向)、-X 方向なら辺の上(+Y方向)にあるかどうかを確認する。
整数のまま条件判定しようとしたけど移項したら正負が変わっちゃうのでんーまぁいいやって double を使った
e が Y 座標に平行だったときはチェックしない
LessFoo は不要だったと思う
O(NlogM + M) くらい？


#define INF 2000000000

class LessFoo {
public:
	bool operator()(const PII& a, const PII& b) const {
		return a.first < b.first;
	}
};

int main() {
	int N, M;
	cin>>N;
	
	vector<PII> A(N);
	int Axmin=INF, Axmax=-INF;
	REP(i, N) {
		cin>>A[i].first>>A[i].second;
		Axmin=min(Axmin, A[i].first);
		Axmax=max(Axmax, A[i].first);
	}
	cin>>M;
	vector<PII> B(M);
	int xmin=INF, xmax=-INF;
	REP(i, M) {
		cin>>B[i].first>>B[i].second;
		xmin=min(xmin, B[i].first);
		xmax=max(xmax, B[i].first);
	}
	if(xmin <= Axmin || Axmax <= xmax) {
		cout<<"NO"<<endl;
		return 0;
	}
	sort(ALL(B));
	
	REP(i, N) {
		int x0 = A[i].first;
		int x1 = A[(i+1)%N].first;
		int y0 = A[i].second;
		int y1 = A[(i+1)%N].second;
		if(x0==x1) continue;
		int i0 = distance(B.begin(), lower_bound(ALL(B), MP(x0, -INF), LessFoo()));
		int i1 = distance(B.begin(), lower_bound(ALL(B), MP(x1, -INF), LessFoo()));
		//cout<<i<<"   "<<A[i].first<<" "<<A[(i+1)%N].first<<" "<<i0<<" "<<i1<<endl;
		
		for(int i=i0;i<i1;i++) {
			double x = B[i].first;
			double y = B[i].second;
			if(!( y < ((double)y1-y0)/(x1-x0)*(x-x0)+y0 )) {
				cout<<"NO"<<endl;
				return 0;
			}
		}
		for(int i=i1;i<i0;i++) {
			double x = B[i].first;
			double y = B[i].second;
			//cout<<x<<" "<<y<<endl;
			//cout<<x0<<" "<<y0<<endl;
			//cout<<x1<<" "<<y1<<endl;
			//cout<<(y - y0)<<" "<<(y1-y0)*(x-x0)<<endl;
			if(!( y > ((double)y1-y0)/(x1-x0)*(x-x0)+y0 )) {
				cout<<"NO"<<endl;
				return 0;
			}
		}
	}
	cout<<"YES"<<endl;
	
	return 0;
}