Cod sursa(job #425427)

Utilizator cristiprgPrigoana Cristian cristiprg Data 25 martie 2010 18:49:00
Problema Poligon Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <cstdio>
#define DIM 1024
#define eps 1e-6
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 pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
	 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}



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 <= m; ++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;
		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;
			}
			
			double xp = ((double)yp - (double)y1) * ((double)x2 - (double)x1) / ((double)y2 -(double) y1) +(double) x1;
//			int xp = (yp - y1) * (x2 - x1) / (y2 - y1) +x1;
//			printf("%lf\n", xp);

		
//			printf("intreg\n");
			
			if (xp >= (double)p[i].x)
				++nr_intersectii;// printf("++1 xp = %lf p[i].x = %d\n", xp, p[i].x);
//			else
	//			printf("7\n");
	
		}
	//	printf ("nr intersectii == %d\n", nr_intersectii);
		if (nr_intersectii % 2 == 1)
			++sol;
	}
	
	/*
	for (int i = 1; i <= m; ++i)
		sol += pmpol
	*/
	f = fopen("poligon.out", "w");
	fprintf(f, "%d\n", sol);
	fclose(f);
	
	return 0;
}