Cod sursa(job #1757453)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 15 septembrie 2016 05:26:18
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.04 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(jos > sus){
			swap(sus, jos); }
		if(x0 == x1 && y0 == y1){
			a = 0, b = 0, c = 0;
			return; }
		// 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; } };

ostream& operator<<(ostream& lhs, const dreapta& rhs){
	return lhs << '(' << rhs.st << ' ' << rhs.dr << ' ' << rhs.jos << ' ' << rhs.sus << ' ' << rhs.a << ' ' << rhs.b << ' ' << rhs.b << ')'; }

int main(){
	double sort_by;
	auto get_sort_by_y = [&sort_by](const dreapta& a)->double{
		if(a.st == a.dr && a.sus == a.jos){
			return (double)a.sus; }
		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, -1, 100000};

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

	sort(begin(xs), end(xs));
	xs.erase(unique(begin(xs), end(xs)), end(xs));

	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(i != xs.size()-1 && 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);

		if(i != xs.size()-1){
			sort_by = ((double)xs[i]+(double)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 = xs.size()-1 - (lower_bound(xs.rbegin(), xs.rend(), x, greater<int>()) - xs.rbegin());
		if(poz == xs.size()){
			continue; }

		auto& drs = (xs[poz] == x ? intervals[2*poz] : intervals[2*poz+1]);

		sort_by = x;
		int poz2 = drs.size()-1 - (lower_bound(drs.rbegin(), drs.rend(), dreapta(-1, y, 60001, y), inv_cmp) - drs.rbegin());
		if(poz2 < drs.size() && drs[poz2].there(x, y)){
			++rez; }
		else if(!(poz2%2)){
			++rez; } }
	g << rez;
	return 0; }