题目来源：http://poj.org/problem?id=2318
题目内容：给定一个矩形盒子（左上和右下端点的坐标），再给定n条线段，将盒子分为n+1份，之后给定m个点的坐标，对于盒子的每一段，输出内部包含的点的个数（边界上的算做盒子内）。
解法分析:核心内容有判断点与线段的关系（其实根本用不上判断点是否在多边形内的算法），二分查找。先读进数据在简单的二分查找即可。
算法如下:
1 #include2 #include 3 #include 4 using namespace std; 5 struct Point 6 { 7 int x, y; 8 }; 9 10 struct Line 11 {12 Point a, b;13 } line[5005];14 15 int ans[5005]; //答案数组 16 17 int Multi(Point p1, Point p2, Point p0) //p2相对p1左转为正 ，叉积 18 {19 return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);20 }21 22 void BSearch(Point a, int n) 23 {24 int l, r, mid;25 26 l = 0; r = n-1;27 while (l < r) 28 {29 mid = (l + r) >> 1; // /230 if (Multi(a, line[mid].a, line[mid].b) > 0) //.a为上边的节点 ,若a节点在盒子中 31 l = mid + 1; //左区间推进 32 else 33 r = mid; //右区间推进 34 }35 if (Multi(a, line[l].a, line[l].b) < 0) //判断边界 36 ans[l]++; 37 else 38 ans[l+1]++;39 }40 41 int main() 42 {43 int n, m, x1, y1, x2, y2;44 int t1, t2;45 Point a;46 while (scanf ("%d", &n) && n) //处理 0 结尾 数据 的 好技巧 47 {48 scanf ("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);49 for (int i = 0; i < n; i++) 50 {51 scanf ("%d%d", &t1, &t2);52 line[i].a.x = t1; //.a为上边的节点 53 line[i].a.y = y1;54 line[i].b.x = t2;55 line[i].b.y = y2;56 }57 memset(ans, 0, sizeof (ans));58 for (int i = 0; i < m; i++) 59 {60 scanf ("%d%d", &a.x, &a.y);61 BSearch(a, n);62 }63 for (int i = 0; i <= n; i++)64 printf ("%d: %d\n", i, ans[i]);65 printf("\n");66 }67 return 0;68 }