题意：一个矩形被分成了n + 1块，然后给出m个点，求每个点会落在哪一块中，输出每块的点的个数
就是判断 点与直线的位置，点在直线的逆时针方向叉积 < 0，点在直线的顺时针方向叉积 > 0
// 可以选择二分查找
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int Max = + ;
int num[Max];
//int ux[Max], dx[Max];
struct Point
{
LL ux, dx;
};
LL Cross(LL x1, LL y1, LL x2, LL y2)
{
return x1 * y2 - y1 * x2;
}
int main()
{
int n, m, x1, x2, y1, y2;
while (scanf("%d", &n) != EOF && n)
{
scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
for(int i = ; i <= n; i++)
scanf("%d%d", &ux[i], &dx[i]);
ux[n + ] = x2; // 把最后边界也算进去
dx[n + ] = x2;
memset(num, , sizeof(num));
int x, y, l, r, mid;
for (int i = ; i <= m; i++)
{
scanf("%d%d", &x, &y);
if (!(x >= x1 && x <= x2 && y >= y2 && y <= y1)) // 不在矩形内
continue;
l = , r = n + ;
while (l < r)
{
mid = (l + r) / ;
if (Cross(x - dx[mid], y - y2, ux[mid] - dx[mid], y1 - y2) > ) // 如果 大于 0 说明 点在直线 右侧，所以改变左区间
l = mid + ;
else
r = mid; // r始终是满足条件的
}
num[r - ]++;
/*
for (int j = 1; j <= n + 1; j++)
{
if ( Cross(x - dx[j], y - y2, ux[j] - dx[j], y1 - y2) <= 0)
{
num[j - 1]++;
break;
}
}
*/
}
for (int i = ; i <= n; i++)
printf("%d: %d\n", i, num[i]);
printf("\n");
}
return ;
}