Cod sursa(job #1173917)

Utilizator ELHoriaHoria Cretescu ELHoria Data 21 aprilie 2014 03:04:16
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <limits>
#include <cmath>

using namespace std;

void readData(int& n,int& m,vector< pair<double, double> >& points) {
	scanf("%d %d", &n, &m);
	points.resize(n);
	for (int i = 0; i < n; i++) {
		scanf("%lf %lf", &points[i].first, &points[i].second);
	}
}

bool pointInPolygon(int& n,vector< pair<double,double> > &polygon,pair<double,double>& p) {
	bool c = 0;
	for (int i = 0, j = n - 1; i < n; j = i++) {
		if (((polygon[i].second > p.second) != (polygon[j].second > p.second)) &&
				(p.first < (polygon[j].first - polygon[i].first) * 
				(p.second - polygon[i].second) / (polygon[j].second - polygon[i].second) 
				+ polygon[i].first)
			)
			c ^= 1;
	}
	return c;
}

int main()
{
	freopen("poligon.in", "r", stdin);
	freopen("poligon.out", "w", stdout);
	int n, m;
	vector< pair<double,double> > points;
	readData(n, m, points);
	pair<double, double> point;
	int ans = 0;
	for (int i = 0; i < m; i++) {
		scanf("%lf %lf", &point.first, &point.second);
		if (pointInPolygon(n, points, point)) {
		//	printf("%.2lf %.2lf\n", point.first, point.second);
			ans++;
		}
	}

	printf("%d\n", ans);
	return 0;
}