利用叉积判断点在线段左边还是右边，，然后进行二分即可
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 5005;int n, m, x1, y1, x2, y2;struct Point {int x, y;Point() {}Point(int x, int y) {this->x = x;this->y = y;}};typedef Point Vector;Vector operator – (Vector A, Vector B) {return Vector(A.x – B.x, A.y – B.y);}struct Seg {Point a, b;Seg() {}Seg(Point a, Point b) {this->a = a;this->b = b;}} seg[N];int ans[N];int Cross(Vector A, Vector B) {return A.x * B.y – A.y * B.x;}void gao(Point p) {int l = 0, r = n;while (l < r) {int mid = (l + r) / 2;if (Cross(seg[mid].a – p, seg[mid].b – p) < 0) r = mid;else l = mid + 1;}ans[l]++;}int main() {while (~scanf("%d", &n) && n) {memset(ans, 0, sizeof(ans));scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);int x, y;for (int i = 0; i < n; i++) {scanf("%d%d", &x, &y);seg[i] = Seg(Point(x, y1), Point(y, y2));}for (int i = 0; i < m; i++) {scanf("%d%d", &x, &y);gao(Point(x, y));}for (int i = 0; i <= n; i++)printf("%d: %d\n", i, ans[i]);printf("\n");}return 0;}
今天又是美好的一天，我要展示出我优秀的一面。不必一味讨好别人
