Cod sursa(job #597264)

Utilizator cnt_tstcont teste cnt_tst Data 21 iunie 2011 16:37:53
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 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],p,m,u;
int bnd,x,y,nrpct,lowerpoints,aa,bb;
double ym1,ym2; i64 cc,d; double u1,u2;

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

pair<pct,pct>S[maxN][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 double fct ( pair<pct,pct> a, int d1, int d2 ){
	if ( a.first.y == a.second.y ){
		return a.first.y;
	}
	aa = a.second.y - a.first.y; bb = a.first.x - a.second.x; cc = 1LL*a.second.x * a.first.y - 1LL*a.first.x * a.second.y;
	u1 = (double)( -cc - 1LL*aa*d1 ) / bb;
	u2 = (double)( -cc - 1LL*aa*d2 ) / bb;
	double rez = (u1 + u2)/2;
	return rez;
}

struct cmp2{
	inline bool operator () ( const pair<pct,pct> &a, const pair<pct,pct> &b ) {
		ym1 = fct(a,D[i],D[i+1]);
		ym2 = fct(b,D[i],D[i+1]);
		return ym1 < ym2;
	}
};

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 < dx ; ++i ){
		for ( j = 1 ; j <= n ; ++j ){
			if ( A[j].x == A[j+1].x ) continue;
			if ( A[j].x < A[j+1].x && A[j].x <= D[i] && A[j+1].x >= D[i+1] ){
				++Nr[i];
				S[i][Nr[i]].first = A[j]; S[i][Nr[i]].second = A[j+1];
				continue;
			}
			if ( A[j].x > A[j+1].x && A[j].x >= D[i+1] && A[j+1].x <= D[i] ){
				++Nr[i];
				S[i][Nr[i]].first = A[j+1]; S[i][Nr[i]].second = A[j];
			}
		}
		sort( S[i]+1,S[i]+Nr[i]+1,cmp2() );
	}
}

inline int cb1 ( int X ){
	
	p = 1; u = dx;
	while ( p <= u ){
		m = (p + u) >> 1;
		if ( X >= D[m] && X <= D[m+1] )
			return m;
		if ( X <= D[m] )
			u = m - 1;
		else
			p = m + 1;
	}
	return p;
}

inline i64 det( pct a, pct b , pct c ){
	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 () {
	
	p = 0; u = Nr[bnd];
	
	while ( p <= u ){
		m = (p + u) >> 1; d = det(S[bnd][m].first,z,S[bnd][m].second);
		if ( d <= 0 )
			p = m + 1;
		else
			u = m - 1;
	}
	return u;
}

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(S[bnd][lowerpoints].first,z,S[bnd][lowerpoints].second) )) )
			++nrpct;
		
	}
	
	fprintf(g,"%d\n",nrpct);
}

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