Cod sursa(job #265868)

Utilizator scvalexAlexandru Scvortov scvalex Data 24 februarie 2009 17:34:24
Problema Poligon Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>

typedef struct {
	int x, y;
} Pair;

int N;
Pair Ps[800];

int is_included(Pair p) {
	int i, j, c = 0;

	for (i = 0, j = N-1; i < N; j = i++) {
		if ((Ps[i].y > p.y) == (Ps[j].y > p.y))
			continue;

		if (p.x >= (Ps[j].x - Ps[i].x) * (p.y - Ps[i].y) / (Ps[j].y - Ps[i].y) + Ps[i].x)
			continue;

		//printf("\tintersects (%d, %d) - (%d, %d)\n", Ps[i].x, Ps[i].y, Ps[j].x, Ps[j].y);
		c = !c;
	}

	return c;
}

int cn(Pair p) {
	int c = 0, i;
	float vt;

	for (i = 0; i < N; ++i) {
		if (  ((Ps[i].y <= p.y) && (Ps[i+1].y > p.y))
		   || ((Ps[i].y > p.y) && (Ps[i+1].y <= p.y))) {
		   	vt = (float)(p.y - Ps[i].y) / (Ps[i+1].y - Ps[i].y);
			if (p.x <= Ps[i].x + vt * (Ps[i+1].x - Ps[i].x))
				++c;
		}
	}
	return (c % 2);
}

int main(int argc, char *argv[]) {
	int M, i, t = 0;
	Pair I;

	FILE *fi = fopen("poligon.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	for (i = 0; i < N; ++i)
		fscanf(fi, "%d %d", &Ps[i].x, &Ps[i].y);
	Ps[N].x = Ps[0].x;
	Ps[N].y = Ps[0].y;
	while (M--) {
		fscanf(fi, "%d %d", &I.x, &I.y);
		//printf("(%d, %d) is\n", I.x, I.y);
		if (cn(I)) {
		//	printf("IN\n");
			++t;
		} else {
		//	printf("OUT\n");
		}
	}
	fclose(fi);

	FILE *fo = fopen("poligon.out", "w");
	fprintf(fo, "%d\n", t);
	fclose(fo);

	return 0;
}