poj 2318叉積解点と直線の関係

点の位置を判断するには、二分法による判断と境界線の相対位置、最終的に点の所在ブロックを決定し、配列、点の位置を判断する際にフォークで方向のある面積を積算する.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
//#include <cmath>
#define MAX 5007

using namespace std;

struct Point 
{
    int x , y;
    Point ( ) : x(0) , y(0) {}
    Point ( int a , int b ) : x(a),y(b){}
}p;

struct Line 
{
    Point up , down;
}l[MAX];

int det ( Point a  , Point b )
{
    return a.x * b.y - a.y*b.x;
}

int n,m,x1,y1,x2,y2,u,d;

int  id ( Point p )
{
    if ( det ( Point ( p.x - l[n].down.x , p.y - l[n].down.y ) ,
         Point ( l[n].up.x - p.x , l[n].up.y - p.y))
            > 0 ) return n+1;
    int left = 1 , right = n , mid;
    while ( left != right )
    {
        mid = left + right >> 1;
       // cout << mid << endl;
        //cout << det ( Point ( p.x-l[mid].down.x , p.y-l[mid].down.y ) ,
           //   Point ( l[n].up.x - p.x , l[mid].up.y - p.y)) << endl;
        if ( det ( Point ( p.x-l[mid].down.x , p.y-l[mid].down.y ) ,
             Point ( l[mid].up.x - p.x , l[mid].up.y - p.y ))
                > 0 )  left  = mid + 1;
        else right = mid;
    }
    return left; 
}

int main ( )
{
    int ans [MAX];
    while ( ~scanf("%d" , &n ),n )
    {
        scanf ( "%d%d%d%d%d" , &m , &x1 , &y1 , &x2 , &y2 );
        memset ( ans , 0 , sizeof ( ans ) );
        for ( int i = 1 ; i <= n ; i++ )
        {
            scanf ( "%d%d" , &l[i].up.x , &l[i].down.x );
            l[i].up.y = y1 , l[i].down.y =y2;
        }
        for ( int i = 1 ; i <= m ; i++ )
        {
            scanf ( "%d%d" , &p.x , &p.y );
            ans[id( p )]++;
        }
        for ( int i = 1 ; i <= n+1 ; i++ )
            printf ( "%d: %d
" , i-1 , ans[i] );
        printf ( "
" );
    }
    
}