Cod sursa(job #784015)

Utilizator danalex97Dan H Alexandru danalex97 Data 4 septembrie 2012 18:31:28
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 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)) )
vector <Banda> Band[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 ;
	
	return make_pair( A2.x , (-c1-a1*A2.x) / b1 );
}

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)
		{
			C = Poly[j];
			D = Poly[j+1];
			if ( C.x > D.x || (C.x==D.x && C.y > D.y) ) swap(C,D);
			
			A = Int(C,D, make_pair(Point[i],0), make_pair(Point[i],Mmax) );
			B = Int(C,D, make_pair(Point[i+1],0), make_pair(Point[i+1],Mmax) );
			
			if ( A.x > B.x || (A.x==B.x && A.y > B.y) ) swap(A,B);
			
			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].push_back( make_band( A,B,Mid(A,B) ) );
		}
		
		sort(Band[i].begin(),Band[i].end());
	}
	
	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 , int(Band[Pl].size())-1 );
		
		Sol+=1-(Nbr%2);
	}
	
	G<<Sol<<'\n';
}