Cod sursa(job #597294)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 21 iunie 2011 17:54:01
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.47 kb
#include<stdio.h>
#include<algorithm>
#include<vector>

#define maxN 805
#define i64 long long

using namespace std;

FILE*f=fopen("poligon.in","r");
FILE*g=fopen("poligon.out","w");

int n,q,i,j,D[maxN],dx,Nr[maxN];
int bnd,x,y,nrpct,lowerpoints;
double xm,ym;
vector< pair<double,int> >S[maxN];

struct pct{
	int x;
	int y;
}A[maxN],B[maxN],z;

struct dreapta{
	int a;
	int b;
	i64 c;
}E[maxN];

struct cmp{
	inline bool operator () ( const pct &a, const pct &b ) {
		if ( a.x != b.x )
			return a.x < b.x;
		return a.y < b.y;
	}
};

inline void citire () {
	
	fscanf(f,"%d %d",&n,&q);
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&A[i].x,&A[i].y);
		B[i] = A[i];
	}
}

inline void first () {
	
	sort( B+1, B+n+1, cmp() ); B[0].x = -(1<<29);
	
	for ( i = 1 ; i <= n ; ++i ){
		if ( B[i].x != B[i-1].x ){
			D[++dx] = B[i].x;
		}
	}
	
	A[n+1] = A[1];
	
	for ( i = 1 ; i <= n ; ++i ){
		E[i].a = A[i+1].y - A[i].y;
		E[i].b = A[i].x - A[i+1].x;
		E[i].c = 1LL*A[i+1].x*A[i].y - 1LL*A[i+1].y*A[i].x;
		if ( E[i].b < 0 ){
			E[i].a *= (-1); E[i].b *= (-1); E[i].c *= (-1);
		}
	}
	
	for ( i = 1 ; i < dx ; ++i ){
		S[i].push_back(make_pair(-1,-1));
		for ( j = 1 ; j <= n ; ++j ){
			if ( A[j].x == A[j+1].x ) continue;
			if ( min(A[j].x,A[j+1].x) <= D[i] && D[i+1] <= max(A[j].x,A[j+1].x) ){
				xm = (double)(D[i+1]+D[i]) / 2;
				ym = (double)(-E[j].c - 1LL*E[j].a * xm) / E[j].b;
				S[i].push_back(make_pair(ym,j)); ++Nr[i];
			}
		}
		sort( S[i].begin(),S[i].end() );
	}
}

inline int cb1 ( int X ){
	
	int pas = 1 << 10,i;
	
	for ( i = 0 ; pas ; pas >>= 1 ){
		if ( i + pas <= dx && D[i+pas] <= X )
			i += pas;
	}
	return i;
}

inline i64 det( pct a, pct b , pct c ){
	if ( a.x > c.x ){
		pct aux; aux = a; a = c; c = aux;
	}
	i64 Det = 1LL*(a.x - c.x) * (b.y - c.y) + 1LL*(a.y - c.y) * (c.x - b.x);
	return Det;
}

inline int cb2 () {
	
	int pas = 1 << 10,i;
	
	for ( i = 0 ; pas ; pas >>= 1 ){
		if ( i + pas <= Nr[bnd] )
			if ( det( A[S[bnd][i+pas].second] , z , A[S[bnd][i+pas].second + 1] ) <= 0 )
				i += pas;
	}
	return i;
}

inline void solve () {
	
	while ( q-- ){
		
		fscanf(f,"%d %d",&x,&y); z.x = x; z.y = y;
		
		if ( x < D[1] || x > D[dx] ){
			continue;
		}
		bnd = cb1(x);
		lowerpoints = cb2();
		
		if ( lowerpoints && ((lowerpoints & 1) || ( !det(A[S[bnd][lowerpoints].second],z,A[S[bnd][lowerpoints].second+1]) )) )
			++nrpct;
		
	}
	
	fprintf(g,"%d\n",nrpct);
}

int main () {
	
	citire();
	first();
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}