Cod sursa(job #784012)

Utilizator danalex97Dan H Alexandru danalex97 Data 4 septembrie 2012 18:21:02
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

ifstream F("poligon.in");
ofstream G("poligon.out");

#define x first
#define y second

#define st second.first
#define dr second.second
#define mid first

typedef pair<double,double> Pair;
typedef pair< Pair,pair<Pair,Pair> > Banda;

const int Nmax = 810;
const int Mmax = 60010;

int N,M,Co,Sol;

Pair Poly[Nmax];
int Point[Nmax];

#define make_band(A,B,C) ( make_pair(C,make_pair(A,B)) )
Banda Band[Nmax][Nmax];
int Contor[Nmax];

Pair Mid(Pair A,Pair B) 
{	
	return make_pair( (A.x+B.x)/2 , (A.y+B.y)/2 ); 
}

Pair Int(Pair A,Pair B,Pair A2,Pair B2)
{
	double a1 = A.y - B.y ;
	double b1 = B.x - A.x ;
	double c1 = - A.y * B.x + B.y * A.x ;

	double a2 = A2.y - B2.y ;
	double b2 = B2.x - A2.x ;
	double c2 = - A2.y * B2.x + B2.y * A2.x ;	
	
	double X = a1*b2-a2*b1==0 ? -1 : (c2*b1-c1*b2) / (a1*b2-a2*b1) ;
	double Y = b1==0 ? ( b2==0 ? -1 : (-c2-a2*X) / b2 ) : (-c1-a1*X) / b1 ;
	
	if ( a1 == 0 )
	{
		Y = b1==0 ? -1 : -c1 / b1;
		X = ( a2==0 || Y==-1 ) ? -1 : - ( b2*Y + c2 ) / a2;
	}
	
	return make_pair( X , Y );
}

int Find_band(Pair P,int Left,int Right)
{
	if ( Left==Right ) 
		return Left;
	int Middle = ( Left+Right ) / 2;
	
	if ( P.x >= Point[Middle] && P.x < Point[Middle+1] )
		return Middle;
	if ( P.x < Point[Middle] )
		return Find_band(P,Left,Middle-1);
	return Find_band(P,Middle+1,Right);
}

#define EPS 0.000001

int Ec(Pair P,Pair A,Pair B)
{
	double a = A.y - B.y ;
	double b = B.x - A.x ;
	double c = - A.y * B.x + B.y * A.x ;
	
	if ( P.x*a+P.y*b+c <= EPS &&  P.x*a+P.y*b+c >= -EPS ) return 0;
	if ( P.x*a+P.y*b+c > 0 ) return 1;
	
	return -1;
}

int Find_line(Pair P,int Pl,int Left,int Right)
{
	if ( Right-Left==1 )
	{
		int Ecu=Ec(P,Band[Pl][Right].st,Band[Pl][Right].dr);
		if ( Ecu==0 ) return 0;
		if ( Ecu==1 ) return Right;
		return Left;
	}
	if ( Left==Right )
		return Left;
	int Middle=(Left+Right)/2;
	
	int Ecu=Ec(P,Band[Pl][Middle].st,Band[Pl][Middle].dr);
	
	if ( Ecu==0 ) return 0;
	if ( Ecu==-1 ) return Find_line(P,Pl,Left,Middle-1);
	
	return Find_line(P,Pl,Middle,Right);
}

int main( void )
{
	F>>N>>M;
	for (int i=1;i<=N;++i)
	{
		double Cx,Cy;
		F>>Cx>>Cy;
		Poly[i]=make_pair(Cx,Cy);
		Point[i]=int(Cx);
	}
	Poly[N+1]=Poly[1];

	sort(Point+1,Point+N+1);
	
	Co=1;
	for (int i=2;i<=N;++i)
	{
		if ( Point[i]==Point[i-1] ) continue;
		Point[++Co]=Point[i];
	}
	for (int i=Co+1;i<=N;++i) Point[i]=0;
	
	for (int i=1;i<Co;++i)
	{
		Pair A,B,C,D;
		
		for (int j=1;j<=N;++j)
		{
			A = Int(Poly[j],Poly[j+1], make_pair(Point[i],0), make_pair(Point[i],Mmax) );
			B = Int(Poly[j],Poly[j+1], make_pair(Point[i+1],0), make_pair(Point[i+1],Mmax) );
			
			C = Poly[j];
			D = Poly[j+1];
			
			if ( A.x > B.x || (A.x==B.x && A.y > B.y) ) swap(A,B);
			if ( C.x > D.x || (C.x==D.x && C.y > D.y) ) swap(C,D);
			
			int Ok=0;
			if ( (A.x > C.x && A.x < D.x) || (B.x > C.x && B.x < D.x) ) Ok=1;
			if ( A.x == C.x ) Ok=1;
			if ( B.x == D.x ) Ok=1;
			
			if ( !Ok ) continue;
			
			Band[i][Contor[i]++]=make_band( A,B,Mid(A,B) );
		}
		
		sort(Band[i],Band[i]+Contor[i]);
		--Contor[i];
	}
	
	while ( M-- )
	{
		Pair P;
		F>>P.x>>P.y;
		
		if ( P.x < Point[1] || P.x > Point[Co] ) continue;
		
		int Pl = Find_band( P , 1 , Co-1 );
		int Val = Ec(P, Band[Pl][0].st, Band[Pl][0].dr );
		
		if ( Val==0 || Val==-1 )
		{
			if ( Val==0 ) ++Co;
			continue;
		}			
		
		int Nbr = Find_line( P , Pl , 0 , Contor[Pl] );
		
		Sol+=1-(Nbr%2);
	}
	
	G<<Sol<<'\n';
}