POJ 2318 TOYS

這題計算幾何的部分還是比較簡單的，重點是那個二分有點麻煩（大牛忽略），每次寫二分自己都得用筆模擬一番，然後才能確定。

因為y1,y2是公共的，所以存儲的時候線段的時候只要存儲x的坐標就可以了。然後就是判斷是在右邊還是在左邊。

#include
#include
#include
#include
using namespace std;
const int N=5005;
struct Line
{
    int x1,x2;
}line[N];
int x1,x2,y1,y2,n,m,num[N];
int judge(int x,int y,int id)
{
   int a1=line[id].x1-x,a2=line[id].x2-x;
   int b1=y1-y,b2=y2-y;
   return a1*b2-a2*b1;
}
int main()
{
    int x,y,k=0;
    while(scanf("%d",&n),n!=0)
    {
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&line[i].x1,&line[i].x2);
        memset(num,0,sizeof(num));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            if(judge(x,y,1)<0)//這裡要注意一下
            {
                num[0]++;
                continue;
            }
            if(judge(x,y,n)>0)//這裡也要注意，通過畫圖可以發現，這裡需要單獨討論一下。
            {
                num[n]++;
                continue;
            }
            int l=1,r=n;//這裡是二分
            while(r-l>1)
            {
                int mid=(l+r)/2;
                if(judge(x,y,mid)<0)
                    r=mid;
                else
                    l=mid;
            }
            num[l]++;
        }
        if(k>0)
            printf("\n");
        k++;
        for(int i=0;i<=n;i++)
            printf("%d: %d\n",i,num[i]);
    }
    return 0;
}