Cod sursa(job #1244568)

Utilizator vladrochianVlad Rochian vladrochian Data 17 octombrie 2014 20:01:48
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.36 kb
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int kMaxVertices = 805;

int N, M, sol;

struct Point {
	int x, y;
	Point() {
		x = 0;
		y = 0;
	}
	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
} vertices[kMaxVertices];

set<pair<int, int>> vertice_set;

struct Line {
	double a, b, c;
	Line() {
		a = 0.0;
		b = 0.0;
		c = 0.0;
	}
	Line(double a, double b, double c) {
		this->a = a;
		this->b = b;
		this->c = c;
	}
	Line(Point p1, Point p2) {
		a = p2.y - p1.y;
		b = p1.x - p2.x;
		c = a * p1.x + b * p1.y;
	}
} edges[kMaxVertices];

set<int> x;
int area_count, vertical_lines[kMaxVertices];
vector<int> area_edges[kMaxVertices], vertical_segments;
double intersection_y[kMaxVertices];

ifstream fin("poligon.in");
ofstream fout("poligon.out");

void ReadPolygon() {
	for (int i = 0; i < N; ++i) {
		fin >> vertices[i].x >> vertices[i].y;
		x.insert(vertices[i].x);
		vertice_set.insert(make_pair(vertices[i].x, vertices[i].y));
	}
	vertices[N] = vertices[0];
	for (int i = 0; i < N; ++i)
		edges[i] = Line(vertices[i], vertices[i + 1]);
}

double IntersectionY(Line l1, Line l2) {
	return (l1.a * l2.c - l2.a * l1.c) / (l1.a * l2.b - l2.a * l1.b);
}

bool CompareLines(int a, int b) {
	return intersection_y[a] < intersection_y[b];
}
bool CompareSegments(int a, int b) {
	if (vertices[a].x == vertices[b].x)
		return vertices[a].y < vertices[b].y;
	return vertices[a].x < vertices[b].x;
}

void BuildAreas() {
	area_count = -1;
	for (auto it : x)
		vertical_lines[++area_count] = it;
	for (int area = 0; area < area_count; ++area) {
		Line mid_line(1.0, 0.0, (vertical_lines[area] + vertical_lines[area + 1]) / 2.0);
		for (int edge = 0; edge < N; ++edge) {
			int x1 = vertices[edge].x, x2 = vertices[edge + 1].x;
			if (x1 > x2)
				swap(x1, x2);
			if (x1 <= vertical_lines[area] && vertical_lines[area + 1] <= x2) {
				area_edges[area].push_back(edge);
				intersection_y[edge] = IntersectionY(edges[edge], mid_line);
			}
		}
		sort(area_edges[area].begin(), area_edges[area].end(), CompareLines);
	}
}

void GetVerticalSegments() {
	for (int line = 0; line < N; ++line)
		if (vertices[line].x == vertices[line + 1].x)
			vertical_segments.push_back(line);
	sort(vertical_segments.begin(), vertical_segments.end(), CompareSegments);
}

bool CheckVertice(int x, int y) {
	return vertice_set.find(make_pair(x, y)) != vertice_set.end();
}

bool CheckOnVerticalEdge(int x, int y) {
	int l = 0, r = vertical_segments.size() - 1, m;
	while (l <= r) {
		m = (l + r) >> 1;
		int sx = vertices[vertical_segments[m]].x, sy1 = vertices[vertical_segments[m]].y, sy2 = vertices[vertical_segments[m] + 1].y;
		if (sy1 > sy2)
			swap(sy1, sy2);
		if (x == sx) {
			if (y < sy1)
				r = m - 1;
			else if (y <= sy2)
				return true;
			else
				l = m + 1;
		} else if (x > sx) {
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	return false;
}

int GetArea(int x) {
    int l = 0, r = area_count, m;
    while (l <= r) {
		m = (l + r) >> 1;
		if (x < vertical_lines[m])
			r = m - 1;
		else
			l = m + 1;
    }
    if (r == area_count && vertical_lines[r] == x)
		--r;
	return r;
}

int Position(int x, int y, int x1, int y1, int x2, int y2) {
	if (x1 > x2) {
		swap(x1, x2);
		swap(y1, y2);
	}
	if (x == x1)
		return y - y1;
	double ps = (double)(y2 - y1)/(x2 - x1), pp = (double)(y - y1)/(x - x1);
	if (pp == ps)
		return 0;
	if (pp < ps)
		return -1;
	return 1;
}

int CountEdges(vector<int> &ls, int x, int y) {
	int l = 0, r = ls.size() - 1, m;
	while (l <= r) {
		m = (l + r) >> 1;
		int pos = Position(x, y, vertices[ls[m]].x, vertices[ls[m]].y, vertices[ls[m] + 1].x, vertices[ls[m] + 1].y);
		if (!pos)
			return 69;
		if (pos < 0)
			r = m - 1;
		else
			l = m + 1;
	}
	return l;
}

bool CheckInPolygon(int x, int y) {
	int area = GetArea(x);
	if (area < 0 || area == area_count)
		return false;
	int edges_under = CountEdges(area_edges[area], x, y);
	if (edges_under & 1)
		return true;
	return false;
}

int main() {
	fin >> N >> M;
	ReadPolygon();
	BuildAreas();
	GetVerticalSegments();
	while (M--) {
		int x, y;
		fin >> x >> y;
		if (CheckVertice(x, y))
			++sol;
		else if (CheckOnVerticalEdge(x, y))
			++sol;
		else if (CheckInPolygon(x, y))
			++sol;
	}
	fout << sol << "\n";
	return 0;
}