Cod sursa(job #784034)

Utilizator danalex97Dan H Alexandru danalex97 Data 4 septembrie 2012 19:17:44
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.4 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> > BNMda;

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

int N,M,Co,Sol,Act;

Pair Poly[Nmax];
int Point[Nmax];
char Str[Pars];

#define make_bNMd(A,B,C) ( make_pair(C,make_pair(A,B)) )
vector <BNMda> BNMd[Nmax];

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

inline Pair Int(Pair A,Pair B,Pair D)
{
	return make_pair(D.x, B.y + (B.y - A.y) * (D.x - B.x) / (B.x - A.x));
}

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

#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 ) return -1;
	if ( P.x*a+P.y*b+c > -EPS ) return 1;
	
	return 0;
}

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

void Get( int& A )
{	A=0;
	while ( Str[Act]>'9' || Str[Act]<'0' ) ++Act;
	while ( Str[Act]>='0' && Str[Act]<='9' ) A=A*10+Str[Act++]-'0';
}

int main( void )
{
	F.getline(Str,Pars,EOF);
	
	Get(N);Get(M);
	for (int i=1;i<=N;++i)
	{
		int Cx,Cy;
		Get(Cx),Get(Cy);
		Poly[i]=make_pair(double(Cx),double(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)
	{
		register Pair A,B,C,D;
		
		for (int j=1;j<=N;++j)
		{
			C = Poly[j];
			D = Poly[j+1];
			if ( C > D ) swap(C,D);
			
			A = Int(C,D, make_pair(Point[i],0) );
			B = Int(C,D, make_pair(Point[i+1],0) );
			if ( A > B ) swap(A,B);
			
			if ( (A.x > C.x && A.x < D.x) || (B.x > C.x && B.x < D.x) || A.x == C.x || B.x == D.x ) 
				BNMd[i].push_back( make_bNMd( A,B,Mid(A,B) ) );
		}
		
		sort(BNMd[i].begin(),BNMd[i].end());
	}
	
	while ( M-- )
	{
		int X,Y;
		
		Get(X);Get(Y);
		Pair P=make_pair(double(X),double(Y));
		
		if ( P.x < Point[1] || P.x > Point[Co] ) continue;
		
		int Pl = Find_bNMd( P , 1 , Co-1 );
		int Val = Ec(P, BNMd[Pl][0].st, BNMd[Pl][0].dr );
		
		if ( Val==0 || Val==-1 )
		{
			if ( Val==0 ) ++Co;
			continue;
		}			
		
		int Nbr = Find_line( P , Pl , 0 , int(BNMd[Pl].size())-1 );
		
		Sol+=1-(Nbr%2);
	}
	
	G<<Sol<<'\n';
}

*/

#include <cmath>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const double eps = 0.0001;

#define x first
#define y second

int N, NM, M;

typedef pair<int,int> Pair;

Pair A[802]; int B[802];

int Sol, Make;
vector<int> V[802];

int wA[802], wB[802], wC[802];
double av1[802], av2[802];
int Var1, Var2;

inline double gety(const int& what, const int& xNow) {	return av1[what] * xNow + av2[what];   }
class Sort {	public: inline bool operator () (const int& i1, const int& i2) {	return (gety(i1, Var1) + gety(i1, Var2) < gety(i2, Var1) + gety(i2, Var2));	}   };

inline bool Int(const int& P, const Pair& p1, const Pair& p2)
{ 	return (P >= min(p1.x, p2.x) && P < max(p1.x, p2.x)); }
inline bool Uper(const Pair& P, const int& what)
{ if (1LL * wA[what] * P.x + 1LL * wB[what] * P.y + wC[what] == 0) Make = 1; return (P.y >= gety(what, P.x)); }

ifstream fin("poligon.in");
ofstream fout("poligon.out");

int main()
{
	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
	{
		fin >> A[i].x >> A[i].y;
		B[i] = A[i].x;
	}
	A[N + 1] = A[1];
	
	for (int i = 1; i <= N; ++i)
	{
		wA[i] = (A[i].y - A[i + 1].y);
		wB[i] = (A[i + 1].x - A[i].x);
		wC[i] = (A[i].x * A[i + 1].y - A[i].y * A[i + 1].x);
		av1[i] = -1.0 * wA[i] / wB[i];
		av2[i] = -1.0 * wC[i] / wB[i];
	}
	
	sort(B + 1, B + N + 1);
	for (int i = 1; i <= N; ++i)
	{
		B[++NM] = B[i];
		while (i < N && B[i] == B[i + 1])
			++i;
	}
	
	for (int i = 1; i <= NM; ++i) 
	{
		for (int j = 1; j <= N; ++j)
			if (Int(B[i], A[j], A[j + 1]))
				V[i].push_back(j);
		
		Var1 = B[i], Var2 = B[i + 1];
		sort(V[i].begin(), V[i].end(), Sort());
	}
	
	Pair Now;
	for (int i = 1; i <= M; ++i)
	{
		fin >> Now.x >> Now.y;
		if (Now.x < B[1] || Now.x > B[NM]) continue;
		
		Make = 0;
		
		int K = 1 << 9, Go, upped;
		for (Go = 0; K; K >>= 1)
			if (Go + K <= NM && B[Go + K] <= Now.x)
				Go += K;
				
		K = 1;
		for (; K <= V[Go].size(); K <<= 1);
		
		upped = 0;
		for (; K; K >>= 1)
			if (upped + K <= V[Go].size() && Uper(Now, V[Go][upped + K - 1]))
				upped += K;
		
		Sol += max(upped % 2, Make);
	}
	
	fout << Sol << '\n';
	
	fin.close();
	fout.close();
}