Cod sursa(job #425316)

Utilizator cristiprgPrigoana Cristian cristiprg Data 25 martie 2010 17:29:42
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#define DIM 1024
struct punct 
{
	int x, y;
} Pol[DIM], p[65536];

int n, m;

int main()
{
	FILE *f = fopen("poligon.in", "r");
	fscanf(f, "%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		fscanf(f, "%d%d", &Pol[i].x, &Pol[i].y);
	for (int i = 1; i <= n; ++i)
		fscanf(f, "%d%d", &p[i].x, &p[i].y);
		
	fclose(f);
	Pol[n+1] = Pol[1];
	int sol = 0;
	for (int i = 1; i <= m; ++i)
	{
		int yp = p[i].y, xp;
		int nr_intersectii = 0;
		for (int j = 1; j <= n; ++j)
		{

			int x1 = Pol[j].x, y1 = Pol[j].y, x2 = Pol[j+1].x, y2 = Pol[j+1].y;
	//		printf("%d %d %d %d %d %d\n", p[i].x, p[i].y, x1, y1, x2, y2);
			
	//		if (p[i].x < x1 && p[i].x < x2){printf ("1\n");	continue;}
			if (p[i].x > x1 && p[i].x > x2){//printf ("2\n");
				continue;}
			
			if (p[i].y < y1 && p[i].y < y2){//printf ("3\n");
				continue;}
			if (p[i].y > y1 && p[i].y > y2){//printf ("4\n");
				continue;}
			
			

			
			if (y2 == y1)
			{
				if (yp == y1)
					if (p[i].x < x1 || p[i].x < x2)
						++nr_intersectii, printf("++\n") ;
			//printf ("5\n");
				continue;
			}
			
			xp = (yp - y1) * (x2 - x1) / (y2 - y1) + x1;
			if (xp >= p[i].x)
				++nr_intersectii;
		}
		
		if (nr_intersectii % 2 == 1)
			++sol;
	}
	
	f = fopen("poligon.out", "w");
	fprintf(f, "%d\n", sol);
	fclose(f);
	
	return 0;
}