Cod sursa(job #385908)

Utilizator ChallengeMurtaza Alexandru Challenge Data 23 ianuarie 2010 19:13:38
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>

const char InFile[]="poligon.in";
const char OutFile[]="poligon.out";
const int MaxN=805;

using namespace std;

struct p2d{
	int x,y;
};

p2d poly[MaxN];
int n,m,in,px,py;
ifstream fin(InFile);
ofstream fout(OutFile);

int minl(int a, int b){
	if(a>b){return b;}else{return a;}
}

int maxl(int a, int b){
	if(a<b){return b;}else{return a;}
}

int main(){
	fin>>n>>m;
	for(register int i=0;i<n;++i){
		fin>>poly[i].x>>poly[i].y;
	}
	poly[n]=poly[0];
	for(register int j=0;j<m;++j){
		fin>>px>>py;
		
		int inter=0;
		for(register int i=0;i<n;++i){
			int a1=poly[i].y-poly[i+1].y;
			int b1=poly[i+1].x-poly[i].x;
			int c1=poly[i].y*poly[i+1].x-poly[i+1].y*poly[i].x;
			
			int tx=px+70;
			int ty=py;
			int a2=py-ty;
			int b2=tx-px;
			int c2=tx*py-px*ty;
			
			if(a2*b1!=a1*b2){
				int ix=-(b1*c2-b2*c1)/(a1*b2-a2*b1);
				int iy=-(c1*a2-c2*a1)/(a1*b2-a2*b1);
				
				if(ix>=px && !(poly[i].x==ix && poly[i].y==iy)){
					int box_up_x=minl(poly[i].x,poly[i+1].x);
					int box_up_y=minl(poly[i].y,poly[i+1].y);
					int box_lo_x=maxl(poly[i].x,poly[i+1].x);
					int box_lo_y=maxl(poly[i].y,poly[i+1].y);
					if(ix>=box_up_x && ix<=box_lo_x && iy>=box_up_y && iy<=box_lo_y){
						++inter;
					}
				}
			}
		}
		
		if(inter%2==1){
			++in;
		}
	}
	fin.close();
	
	fout<<in;
	fout.close();
}