Cod sursa(job #1758654)

Utilizator retrogradLucian Bicsi retrograd Data 17 septembrie 2016 16:44:59
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxC = 60005;

typedef pair<int, int> Point;
#define x first
#define y second

Point P[1005];
vector<int> Enter[kMaxC], Exit[kMaxC], Q[kMaxC];
vector<pair<int, int>> Verts[kMaxC]; 
int n;

#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

void Debug(string);

struct LineSet {

	struct cmp {
		static int x;

		static long double evaluate_line(int i) {
			// Evaluate line i at coord x
			// y(x) = y0 + (x - x0) * (dy / dx)
			return P[i - 1].y + 1.0 * (x - P[i - 1].x) * (P[i].y - P[i - 1].y) / (P[i].x - P[i - 1].x);
		}

		bool operator()(const int &a, const int &b) const {
			return evaluate_line(a) < evaluate_line(b);
		}
	};

	typedef tree <
	   int, // Key Type
	   null_type, // Mapped type
	   cmp, // Compare functor
	   rb_tree_tag, // Tree tag: [rb_tree_tag|splay_tree_tag|ov_tree_tag]
	   tree_order_statistics_node_update // Update policy
	> ordered_set;
	
	ordered_set Set;

	void ChangeX(int nw) {cmp::x = nw;}
	void Insert(int i) {
		Set.insert(i);
		// Debug("Inserted: " + to_string(i));
	}
	void Erase(int i) {
		Set.erase(i);
		// Debug("Erased: " + to_string(i));
	}

	bool Solve(int y) {
		P[n + 1] = Point(cmp::x, y);
		P[n + 2] = Point(cmp::x + 1, y);

		auto it = Set.lower_bound(n + 2);

		if(it == Set.end()) return 0;

		// Debug("Iterator has value: " + to_string(*it));
		if(cmp::evaluate_line(*it) == y) return true;

		Debug(to_string(Set.order_of_key(n + 2)));

		return (Set.order_of_key(n + 2) % 2);
	}
};
int LineSet::cmp::x = 0;


void Debug(string message) {
	cerr << "[" << LineSet::cmp::x << "] " << message << '\n';
}

LineSet Set;

int Solve() {
	int ans = 0;

	for(int cur_x = 0; cur_x <= 60000; ++cur_x) {
		auto &enter = Enter[cur_x];
		auto &exit = Exit[cur_x];
		auto &verts = Verts[cur_x];

		Set.ChangeX(cur_x);

		for(int i : enter) Set.Insert(i);

		sort(verts.begin(), verts.end());
		for(auto cur_y : Q[cur_x]) {
			// Check in verts
			auto it = lower_bound(verts.begin(), verts.end(), make_pair(cur_y, 100000));
			if(it != begin(verts)) {
				--it;
				assert(it->first <= cur_y);
				if(it->second >= cur_y) {
					ans += 1;
					// Debug("Got(from vertical): " + to_string(cur_y));
					continue;
				}
			}

			if(Set.Solve(cur_y)) {
				ans += 1;
				// Debug("Got(from oblique): " + to_string(cur_y));
			}
		}

		for(auto i : exit) Set.Erase(i);
	}

	return ans;
}

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

	int m;
	cin >> n >> m;

	for(int i = 1; i <= n; ++i)
		cin >> P[i].x >> P[i].y;
	P[0] = P[n];

	for(int i = 1; i <= n; ++i) {
		int x1 = P[i - 1].x;
		int x2 = P[i].x;

		if(x1 == x2) {
			int y1 = P[i - 1].y;
			int y2 = P[i].y;

			if(y1 < y2) Verts[x1].emplace_back(y1, y2 - 1);
			else Verts[x1].emplace_back(y2 + 1, y1);
			continue;
		}

		if(x1 < x2) --x2;
		else {
			swap(x1, x2);
			++x1;
		}

		Enter[x1].push_back(i);
		Exit[x2].push_back(i);
	}

	for(int i = 1; i <= m; ++i) {
		int x, y;
		cin >> x >> y;
		Q[x].push_back(y);
	}

	cout << Solve() << endl;

	return 0;
}