Cod sursa(job #1748035)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 25 august 2016 23:24:47
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 850
#define MAXM 60050

using namespace std;

struct coord
{
    int x, y;
    coord(int x = 0, int y = 0) : x(x), y(y) { }
    bool operator()(coord a, coord b)
    {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};
int n, m;
coord polygon[MAXN];
coord infra[MAXM];
double a[MAXN], b[MAXN], c[MAXN];
vector<int> xes;
vector<int> banda[MAXN];
int cmpxind;
const double EPS = 0.000000008;
inline bool equals(double e, double f)
{
    return (e-f) >= -EPS && (e-f) <= EPS;
}


bool cmp(int i, int j)
{
    double y1 = (-c[i] - a[i] * xes[cmpxind]) / b[i];
    //double y2 = polygon[i+1].x > xes[cmpxind+1] ? (-c[i] - a[i] * xes[cmpxind+1]) / b[i] : polygon[i+1].y;
    double y2 = (-c[i] - a[i] * xes[cmpxind+1]) / b[i];
	double yi = (y1+y2); // /2
	y1 = (-c[j] - a[j] * xes[cmpxind]) / b[j];
    y2 = (-c[j] - a[j] * xes[cmpxind+1]) / b[j];
	double yj = (y1+y2); // /2
	return yi < yj;
}

void citire()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
		scanf("%d %d", &polygon[i].x, &polygon[i].y);
    for (int i = 1; i <= m; i++)
		scanf("%d %d", &infra[i].x, &infra[i].y);
}

void prepare()
{
	/// precalc ecuations
	polygon[n+1] = polygon[1];
    for (int i = 1; i <= n; i++) {
		coord p1 = polygon[i];
		coord p2 = polygon[i+1];
        a[i] = p1.y - p2.y;
        b[i] = p2.x - p1.x;
        c[i] = p1.x*p2.y - p2.x*p1.y;
    }
    vector<int> temp;
    for (int i = 1; i <= n; i++)
        temp.push_back(polygon[i].x);
	sort(temp.begin(), temp.end());
    xes.push_back(temp.front());
    for (int i = 1; i < n; i++)
		if (temp[i] != temp[i-1])
			xes.push_back(temp[i]);
	xes.push_back(temp.front());
    for (int i = 0; i < xes.size()-1; i++) {
		cmpxind = i;
        for (int j = 1; j <= n; j++) {
			coord p1 = polygon[j];
			coord p2 = polygon[j%n + 1];
            if (min(p1.x, p2.x) <= xes[i] && max(p1.x, p2.x) > xes[i])
				banda[i].push_back(j);
        }
        sort(banda[i].begin(), banda[i].end(), cmp);
        //printf("%d\n", banda[i].size());
    }
}


bool sub(int lix, coord p, int &ed)
{
    if (equals(a[lix]*p.x + b[lix]*p.y + c[lix], 0)) ed = 1;
    double y1 = (-c[lix] - a[lix] * p.x) / b[lix];
	return (p.y >= y1);
}

void solve()
{
    int rez = 0;
    for (int i = 1; i <= m; i++) {
        int val = 0;
        int cs = 1, cf = xes.size()-1;
        for (cs; cs < xes.size(); cs <<= 1);
        for (int step = cs; step; step >>= 1)
            if (val + step < cf && xes[val+step] < infra[i].x)
				val += step;
		if (infra[i].x < xes[val]) continue;
		cf = banda[val].size();
        for (cs = 1; cs <= cf; cs <<= 1);
        int cate = 0, ed = 0;
        for (int step = cs; step; step >>= 1) {
			if (cate + step <= cf && sub(banda[val][cate+step-1], infra[i], ed))
				cate += step;
        }
        rez += (ed || (cate & 1));
    }
    printf("%d", rez);
}

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

	citire();
    prepare();
    solve();

    return 0;
}