Cod sursa(job #425360)

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

int n, m;

bool pe_latura(int x, int y, int x1, int y1, int x2, int y2)
{
	if ( (y1-y2)*x + (x2-x1)*y + x1*y2 - y1*x2 == 0)
		return true;
	return false;
}

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 ("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 (pe_latura(p[i].x, p[i].y, x1, y1, x2, y2))
				if (p[i].x <= x1 && p[i].x >= x2 || p[i].x <= x2 && p[i].x >= x1)
				if (p[i].y <= y1 && p[i].y >= y2 || p[i].y <= y2 && p[i].y >= y1)
						{	nr_intersectii = 10001;	break;}

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