Cod sursa(job #1756526)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 12 septembrie 2016 23:46:26
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>
using namespace std;

struct dreapta{
	int st, dr, sus, jos;
	double a, b, c;
	dreapta(const int x0, const int y0, const int x1, const int y1): st(x0), dr(x1), sus(y0), jos(y1){
		if(st > dr){
			swap(st, dr); }
		if(sus < jos){
			swap(sus, jos); }
		// ax + by = c
		a = y1-y0, b = -x1+x0;
		c = a*x0 + b*y0; }
	bool there(const double x, const double y)const{
		return a * x + b * y == c && st <= x && x <= dr && jos <= y && y <= sus; }
	double operator()(const double x)const{
		if(b == 0){
			return min(sus, jos); }
		return (c - a*x) / b; } };

int main(){
	double sort_by;
	auto get_sort_by_y = [&sort_by](const dreapta& a){
		return a.st != a.dr ? a(sort_by) : a.jos + 0.5; };

	auto cmp = [&](const dreapta& a, const dreapta& b){
		return get_sort_by_y(a) < get_sort_by_y(b); };
	auto inv_cmp = [&](const dreapta& a, const dreapta& b){
		return get_sort_by_y(a) > get_sort_by_y(b); };

	ifstream f("poligon.in");
	ofstream g("poligon.out");

	int n, m;
	f >> n >> m;

	int x0, y0;
	f >> x0 >> y0;

	vector<dreapta> drepte;
	vector<int> xs = {x0};
	int xc, yc;
	for(int i = 1, xp = x0, yp = y0; i < n; ++i){
		f >> xc >> yc;
		xs.push_back(xc);
		drepte.emplace_back(xp, yp, xc, yc);
		xp = xc, yp = yc; }
	drepte.emplace_back(xc, yc, x0, y0);

	sort(begin(xs), end(xs));
	xs.erase(unique(begin(xs), end(xs)), end(xs));
	xs.insert(begin(xs), -1);
	xs.push_back(60001);

	vector<vector<dreapta>> intervals(2*xs.size());
	// intervals[2*i] = dreptele ce-s fix prin xs[i];
	// intervals[2*i+1] = dreptele ce-s in intervalul (xs[i], xs[i+1])

	for(const auto d : drepte){
		for(int i = 0; i < xs.size(); ++i){
			if(d.st <= xs[i] && xs[i] <= d.dr){
				intervals[2*i].push_back(d); }
			if(d.st <= xs[i] && xs[i+1] <= d.dr){
				intervals[2*i+1].push_back(d); } } }

	for(int i = 0; i < xs.size(); ++i){
		sort_by = xs[i];
		sort(begin(intervals[2*i]), end(intervals[2*i]), cmp);
		sort_by = ((double)xs[i]+xs[i+1]) / 2.0;
		sort(begin(intervals[2*i+1]), end(intervals[2*i+1]), cmp); }

	int rez = 0;
	for(int i = 0, x, y; i < m; ++i){
		f >> x >> y;
		int poz = n-1 - (lower_bound(xs.rbegin(), xs.rend(), x, greater<int>()) - xs.rbegin());
		auto& drs = (xs[poz] == x ? intervals[2*poz] : intervals[2*poz+1]);

		sort_by = (xs[poz] == x ? x : (double)(xs[poz] + xs[poz+1]) / 2.0);
		int poz2 = drs.size()-1 - (lower_bound(drs.rbegin(), drs.rend(), dreapta(-1, y, 60001, y), inv_cmp) - drs.rbegin());
		if(xs[poz] == x){
			if(poz2 != 0 && poz2 <= drs.size() && drs[poz2-1].there(x, y)){
				++rez; }
			if(poz2 < drs.size() && drs[poz2].there(x, y)){
				++rez; } }
		else{
			if(poz2 >= drs.size()){
				continue; }
			if(drs[poz2].there(x, y)){
				++rez; }
			else{
				rez += (poz2^1) % 2; } } }
	g << rez;
	return 0; }