Cod sursa(job #346670)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 8 septembrie 2009 23:21:49
Problema Poligon Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
// Time Complexity : O(N * M)

#include <stdio.h>
#include <math.h>

#define NMAX 1010
#define eps 1e-7

int x[NMAX], y[NMAX], xx, yy;
int i, j, k, N, M, np;

int semn(long long a, long long b, long long c, double x, double y)
{
	double r = a*x + b*y + c;

	if (fabs(r) < eps) return 0;
	else
	if (r > 0)
		return 1;
	else
		return -1;
}

int parallel(long long a1, long long b1, long long a2, long long b2)
{
	return (a2*b1 - a1*b2 == 0);
}

int inbetween(int a, int b, double c)
{
	if (fabs(a-c) < eps || fabs(b-c) < eps || (a <= c && c <= b) || (b <= c && c <= a))
		return 1;
	else
		return 0;
}

int onsegment(int xa, int ya, int xb, int yb, double x, double y)
{
	long long a, b, c;

	a = ya - yb;
	b = xb - xa;
	c = (long long)(xa) * (long long)(yb) - (long long)(xb) * (long long)(ya);

	return (inbetween(xa,xb,x) && inbetween(ya,yb,y) && semn(a,b,c,x,y)==0);
}

int intersect(int x1a, int y1a, int x1b, int y1b,
	          int x2a, int y2a, int x2b, int y2b)
{
	long long a1, b1, c1, a2, b2, c2;
	double xi, yi;

	a1 = y1a - y1b;
	b1 = x1b - x1a;
	c1 = (long long)(x1a) * (long long)(y1b) - (long long)(x1b) * (long long)(y1a);

	a2 = y2a - y2b;
	b2 = x2b - x2a;
	c2 = (long long)(x2a) * (long long)(y2b) - (long long)(x2b) * (long long)(y2a);

	if (parallel(a1, b1, a2, b2))
		return 0;
	else
	{
		xi = (double)(b2*c1-b1*c2) / (double)(a2*b1-a1*b2);
		yi = (double)(c2*a1-c1*a2) / (double)(a2*b1-a1*b2);

		if (onsegment(x1a, y1a, x1b, y1b, xi, yi) &&
			onsegment(x2a, y2a, x2b, y2b, xi, yi))
			return 1;
		else
			return 0;
	}
}

int insidepoly(int xp, int yp)
{
	int xfar, yfar, xdummy, ydummy;
	int i, count = 0;

	for (i = 0; i < N; i++)
		if (onsegment(x[i], y[i], x[i + 1], y[i + 1], xp, yp))
			return 1;

	xfar = 66666;
	yfar = yp + 1;

	for (i = 0; i < N; i++)
		count += intersect(xp, yp, xfar, yfar, x[i], y[i], x[i+1], y[i+1]);

	return count % 2;
}

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

	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
		scanf("%d %d", &x[i], &y[i]);

	x[N] = x[0], y[N] = y[0];

	np = 0;

	for (k = 0; k < M; k++)
	{
		scanf("%d %d", &xx, &yy);
		np += insidepoly(xx, yy);
	}

	freopen("poligon.out", "w", stdout);
	printf("%d\n", np);

	return 0;
}