Cod sursa(job #1873991)

Utilizator doc2177Dorian Croitoru doc2177 Data 9 februarie 2017 16:17:23
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 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, x[800], y[800], ans=0;
cin >> N >> M;

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

for (int i=0; i!=M; ++i) {
	cin >> a >> b ;
	const int init = orient(a,b,x[N-1],y[N-1],x[0],y[0]); 
	if (init==0) ans++ ;
	else {
		int found=0;
		for (int j=0; j!=N-1; ++j) {
			int tmp = orient(a,b,x[j],y[j],x[j+1],y[j+1])/init ;
			if (tmp==0) break;
			if (tmp<0) { found=1; break;}
			}
		if (found==0) ans++;
		}
	}
cout << ans << endl; 
return 0;
}