Cod sursa(job #1808751)

Utilizator retrogradLucian Bicsi retrograd Data 18 noiembrie 2016 01:16:48
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <bits/stdc++.h>

using namespace std;

#define double long double

typedef complex<double> Point;

const double kRotAng = 0;// 441.3128;
const double kEps = 1e-9;

Point Rotate(Point p) {
	return Point(
		p.real() * 3.1241412 + p.imag() * 3.12124124, 
		p.real() * 1.1281251 + p.imag() * 3.11421281
	);
}

double det(Point a, Point b, Point c) {
	return (conj(b - a) * (c - a)).imag();
}

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

	int n, m;
	cin >> n >> m;

	vector<Point> P(n);
	for(int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		P[i] = Rotate(Point(a, b));
	}
	P.push_back(P.front());

	vector<pair<Point, Point>> Edges;
	for(int i = 1; i <= n; ++i) {
		Edges.emplace_back(P[i - 1], P[i]);
	}

	for(auto &e : Edges) {
		if(e.first.real() > e.second.real() + kEps)
			swap(e.first, e.second);
	}


	sort(Edges.begin(), Edges.end(), [](pair<Point, Point> a, pair<Point, Point> b) {
		if(norm(a.first - b.first) < kEps)
			return a.second.imag() < b.second.imag();
		return a.first.imag() < b.first.imag();
	});


	vector<pair<double, int>> Upd;
	vector<pair<Point, int>> Qry(m);

	for(int ei = 0; ei < Edges.size(); ++ei) {
		auto e = Edges[ei];
		Upd.emplace_back(e.first.real() - kEps, ei + 1);
		Upd.emplace_back(e.second.real() + kEps, -(ei + 1));	
	}

	int ans = 0;

	for(int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		Qry[i] = {Rotate(Point(a, b)), i};
	}

	sort(Qry.begin(), Qry.end(), [](pair<Point, int> a, pair<Point, int> b) {
		return a.first.real() + kEps < b.first.real();
	});
	sort(Upd.begin(), Upd.end());

	vector<int> Active;

	auto it = Upd.begin();
	for(auto &q : Qry) {
		while(it != Upd.end() && it->first < q.first.real()) {
			if(it->second < 0) Active.erase(lower_bound(Active.begin(), Active.end(), -(it->second)));
			else Active.insert(lower_bound(Active.begin(), Active.end(), it->second), it->second);
			++it;
		}

		/*for(auto p : Edges) {
			cerr << "<" << p.first << " " << p.second << "> ";
		}
		cerr << endl;*/

		auto it = partition_point(Active.begin(), Active.end(), [&](int x) {
			return det(Edges[x - 1].first, Edges[x - 1].second, q.first) > kEps;
		});
		if(it != Active.end() && abs(det(Edges[*it - 1].first, Edges[*it - 1].second, q.first)) < kEps) {
			// cerr << "Point: " << q.first << " on boundary\n";
			ans += 1;
		} else if((it - Active.begin()) % 2) {
			// cerr << "Point: " << q.first << " on interior\n";
			ans += 1;
		} else {
			// cerr << "Point: " << q.first << " on exterior\n";
		}
	}

	cout << ans << endl;

	return 0;
}