Pagini recente » Profil 6qqqqqq | Cod sursa (job #2968389) | Cod sursa (job #2486342) | Cod sursa (job #1343444) | Cod sursa (job #1663018)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin( "poligon.in" ); ofstream fout( "poligon.out" );
const int nmax = 800;
const int inf = 60000 + 1;
const double eps = 1e-8;
int n, nrf, nrf2;
struct pct{
double x, y;
pct() {}
pct( int _x, int _y ) {
x = _x, y = _y;
}
inline bool operator < ( const pct &a ) const {
return ( (x != a.x) ? (x < a.x) : (y < a.y) );
}
} v[ nmax + 1 ];
int f[ nmax + 2 ];
vector< pct > l[ nmax + 2 ];
void calc_fasii() {
f[ 0 ] = 0;
sort( f + 1, f + n + 1 );
nrf = unique( f + 1, f + n + 1 ) - f;
-- nrf;
f[ nrf + 1 ] = inf;
for( nrf2 = 1; (nrf2 << 1) <= nrf + 1; nrf2 <<= 1 ) {
}
}
double intersectia_cu_vert( pct a, pct b, double k ) {
return (b.y - a.y) * (k - a.x) / (b.x - a.x) + a.y;
}
double egal( double a, double b ) {
return ( a - eps < b && b < a + eps );
}
void calc_intersectii() {
for( int i = 0; i <= nrf; ++ i ) {
for( int j = 0; j < n; ++ j ) {
pct a = v[ j ], b = v[ (j + 1) % n ];
if ( a.x > b.x ) {
pct aux = a; a = b; b = aux;
}
if ( a.x != b.x && a.x <= f[ i ] && f[ i + 1 ] <= b.x ) {
pct p;
p.x = intersectia_cu_vert( a, b, f[ i ] );
p.y = intersectia_cu_vert( a, b, f[ i + 1 ] );
l[ i ].push_back( p );
}
}
l[ i ].push_back( pct( -1, -1 ) );
sort( l[ i ].begin(), l[ i ].end() );
}
}
int solve( pct x ) {
int fasie = 0;
for( int step = nrf2; step > 0; step >>= 1 ) {
if ( fasie + step <= nrf + 1 && f[ fasie + step ] <= x.x ) {
fasie += step;
}
}
int ans = 0;
for( int step = (1 << 9); step > 0; step >>= 1 ) {
if ( ans + step < ( int )l[ fasie ].size() ) {
pct a, b;
a = pct( f[ fasie ], l[ fasie ][ ans + step ].x );
b = pct( f[ fasie + 1 ], l[ fasie ][ ans + step ].y );
double yy = intersectia_cu_vert( a, b, x.x );
if ( yy < x.y ) {
ans += step;
} else if ( yy == x.y ) {
return 1;
}
}
}
return (ans % 2);
}
int main() {
int m;
fin >> n >> m;
for( int i = 0; i < n; ++ i ) {
fin >> v[ i ].x >> v[ i ].y;
f[ i + 1 ] = v[ i ].x;
}
calc_fasii();
calc_intersectii();
int ans = 0;
for( int i = 0; i < m; ++ i ) {
pct q;
fin >> q.x >> q.y;
ans += solve( q );
}
fout << ans << "\n";
fin.close();
fout.close();
return 0;
}