POJ 2318 TOYS 计算几何 判断点在线段的哪一侧

#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>
#include <functional>
#include <vector>
#include <iomanip>
#include <cmath>
#include <iostream>
#include <sstream>
#include <stack>
#include <set>
#include <bitset>
using namespace std;

const int MAX = 5050;

struct Vector
{
    int x, y;
    Vector() = default;
    Vector(int xx, int yy) : x(xx), y(yy) {}
    Vector operator-(const Vector &a) const
    {
        return Vector(x - a.x, y - a.y);
    }
    int operator^(const Vector &a) const
    {
        return x * a.y - y * a.x;
    }
};

typedef Vector Point;

struct Segment
{
    Point s, e;
    Segment() = default;
    Segment(Point ss, Point ee) : s(ss), e(ee) {}
};

int CrossProduct(const Point &p0, const Point &p1, const Point &p2)
{
    return (p1 - p0) ^ (p2 - p0);
}

Segment Ss[MAX];
int Ans[MAX];

int main()
{
    cin.sync_with_stdio(false);
    int n, m, x1, y1, x2, y2, a, b;
    while (cin >> n && n)
    {
        memset(Ans, 0, sizeof(Ans));
        cin >> m >> x1 >> y1 >> x2 >> y2;
        for (int i = 0; i < n; i++)
        {
            cin >> a >> b;
            Ss[i] = Segment(Point(a, y1), Point(b, y2));
        }
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b;
            Point temp(a, b);
            int l = 0, r = n - 1, mid;
            while (l < r)
            {
                mid = (l + r) >> 1;
                if (CrossProduct(temp, Ss[mid].s, Ss[mid].e) > 0)
                    l = mid + 1;
                else
                    r = mid;
            }
            if (CrossProduct(temp, Ss[l].s, Ss[l].e) < 0)
                Ans[l]++;
            else
                Ans[l + 1]++;
        }
        for (int i = 0; i <= n; i++)
            cout << i << ": " << Ans[i] << '\n';
        cout << '\n';
    }
    return 0;
}