题意：将m个玩具扔进一个从左到右分成n个块的箱子中，问每个分块里有多少个玩具（箱子的左上角坐标为(x1, y1)，箱子右下角坐标为(x2, y2)，中间n条分隔栏的上坐标的横坐标为U[i]，下坐标的横坐标为L[i]）。
题目链接：http://poj.org/problem?id=2318
——>>人生第一道ACM几何题目！翻了一下白书加强版——汝佳的《训练指南》，恰恰有判断点在多边形内的方法——转角法，写上submit，处理不好，得了个TLE，Google一下，看到了“二分”这个字眼，立马回到自己的代码，将原来的两个for寻找点的位置换成二分分块寻找点的位置（用叉积判断点在目前探寻边的左边还是右边），submit，这次得了个PE，回看题目：“Separate the output of different problems by a single blank line.”，难道说最后一组数据也要空行（其实已经可以肯定），再改，125MS——AC！
#include <cstdio>
#include <cmath>
#include <cstring>using namespace std;const int maxn = 5000 + 10; //0 < n <= 5000, 0 < m <= 5000
const double eps = 1e-10; //为了精度
int cnt[maxn]; //各个分块的玩具数量
struct Point //点数据类型
{double x, y;Point(double x = 0, double y = 0):x(x), y(y){}
};
typedef Point Vector; //引用为向量类型
Vector operator - (Vector A, Vector B) //重载-运算符
{return Vector(A.x-B.x, A.y-B.y);
}
int dcmp(double x) //为了精度
{if(fabs(x) < eps) return 0;else return x < 0 ? -1 : 1;
}
double Cross(Vector A, Vector B) //叉积函数
{return A.x*B.y - A.y*B.x;
}
Vector U[maxn], L[maxn]; //输入的上部点与下部点
int main()
{int n, m, i;double x1, y1, x2, y2;while(~scanf("%d", &n)){if(!n) return 0;scanf("%d%lf%lf%lf%lf", &m, &x1, &y1, &x2, &y2);for(i = 1; i <= n; i++) //将箱子的左端存了U[0]与L[0]，故输入的边从1开始{scanf("%lf%lf", &U[i].x, &L[i].x);U[i].y = y1;L[i].y = y2;}U[0].x = x1; U[0].y = y1; //箱子左端L[0].x = x1; L[0].y = y2;U[n+1].x = x2; U[n+1].y = y1; //箱子右端L[n+1].x = x2; L[n+1].y = y2;memset(cnt, 0, sizeof(cnt)); //初始化Point p;for(i = 1; i <= m; i++){scanf("%lf%lf", &p.x, &p.y);int l = 0, r = n+1; //二分确定位置while(l < r){int M = l + (r - l) / 2;if(dcmp(Cross(U[M]-L[M], p-L[M])) > 0) r = M;else l = M+1;}cnt[l-1]++;}for(i = 0; i <= n; i++) printf("%d: %d\n", i, cnt[i]);printf("\n"); //气！开始理解为最后一组不用空行，PE了一次}return 0;
}