POJ 2318 TOYS (叉积+二分)

http://poj.org/problem?id=2318
题意：一些斜线将矩形划分成若干个格子，给出一些点，问每个格子里有多少点。

对于一个点和一个线段，可以通过分别连接这个点与线段的两个端点得到两个向量（均是以那个点为起点指向两个端点），然后作叉积得到该点位于线段在左侧还是右侧，叉积大于零为右侧，小于零为左侧。
然后该题就可以利用此性质，发现点对于每个分隔线的叉积具有单调性，通过二分即可解决。

#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>using namespace std;struct node{
    int ux,uy,lx,ly;
}a[5050];
int n,m;
int s[5050];int chaji(int x1,int y1,int x2,int y2)
{
    return x1*y2-x2*y1;
}void work(int x,int y)
{
    //printf("%d %d\n",x,y);int l=0,r=n,mid;int tx1,ty1,tx2,ty2;while(r>l){
    mid=(l+r)/2+1;tx1=x-a[mid].ux;ty1=y-a[mid].uy;tx2=x-a[mid].lx;ty2=y-a[mid].ly;//printf("%d %d %d %d\n",tx1,ty1,tx2,ty2);//printf("%d\n",chaji(tx1,ty1,tx2,ty2));if(chaji(tx1,ty1,tx2,ty2)>0)l=mid;elser=mid-1;}mid=(l+r)/2;s[mid]++;
}int main()
{
    int x,y,X1,Y1,X2,Y2;while(1){
    scanf("%d",&n);if(n==0) break;memset(s,0,sizeof(s));scanf("%d%d%d%d%d",&m,&X1,&Y1,&X2,&Y2);a[0].ux=X1;a[0].uy=Y1;a[0].lx=X1;a[0].ly=Y2;for(int i=1;i<=n;i++){
    scanf("%d%d",&x,&y);a[i].ux=x;a[i].uy=Y1;a[i].lx=y;a[i].ly=Y2;}for(int i=1;i<=m;i++){
    scanf("%d%d",&x,&y);work(x,y);}for(int i=0;i<=n;i++){
    printf("%d: %d\n",i,s[i]);}printf("\n");}return 0;
}