Cod sursa(job #1874015)

Utilizator doc2177Dorian Croitoru doc2177 Data 9 februarie 2017 16:43:13
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

int orient(long & x1, long & y1, long & x2, long & y2, long & x3, long & y3) {
	const long a = (x1-x3)*(y2-y3) - (x2-x3)*(y1-y3);
	if (a>0) return 1;
	if (a<0) return -1;
	return 0;
}

int main() {
freopen("poligon.in","r",stdin);
freopen("poligon.out","w",stdout);

long N,M, a,b, ans=0;
cin >> N >> M;

long x[N], y[N];
for (int i=0; i!=N; ++i) cin >> x[i] >> y[i] ;

for (int i=0; i!=M; ++i) {
	cin >> a >> b ;
	int s=0;
	while (orient(a,b,x[s],y[s],x[s+1],y[s+1])==0) s++;
	int init = orient(a,b,x[s],y[s],x[s+1],y[s+1]);
	
	int found=0;
	for (int j=1; j!=N; ++j) 
		if (orient(a,b,x[(s+j)%N],y[(s+j)%N],x[(s+j+1)%N],y[(s+j+1)%N]) == -init) { 
			found=1; 
			break;
			}
	if (found==0) ans++;
	}

cout << ans << endl; 
return 0;
}