【POJ-2318】TOYS【叉积判定三点旋向】

【POJ-2318】TOYS【叉积判定三点旋向】

问题链接:https://vjudge.net/problem/POJ-2318

Solution:

使用叉积能够判断三个点是顺时针(clockwise)还是逆时针(counterclockwise),之后用二分搜索,注意到按照下面程序的方法,点一定是最后趋向的那个值所在线段的左边。

【注:为什么手动实现Fast I/O的read函数会TLE。。】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int LIM = 5000 + 10;
int ans[LIM];
int xs[LIM], xe[LIM];
int cnt[LIM];

void read(int &x) {
    char ch = getchar();
    x = 0;
  for (; ch < '0' || ch > '9'; ch = getchar());
  for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

int cross(int ax, int ay, int bx, int by) {
    int tmp = ax * by - bx * ay;
    if (tmp == 0) return 0;
    else if (tmp < 0) return -1;
    else return 1;
}

int main(void) {
    int n, m, x1, y1, x2, y2, a, b;
    for (int k = 0; ~scanf("%d", &n) && n; k++) {
        if (k) putchar('\n');
        memset(cnt, 0, sizeof cnt);
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        // read(m);
        // read(x1);
        // read(y1);
        // read(x2);
        // read(y2);
        for (int i = 0; i < n; i++) {
            // read(xs[i]);
            // read(xe[i]);
            scanf("%d%d", xs + i, xe + i);
        }
        for (int i = 0; i < m; i++) {
            // read(a);
            // read(b);
            scanf("%d%d", &a, &b);
            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                int flag = cross(a - xe[mid], b - y2, xs[mid] - xe[mid], y1 - y2);
                if (flag < 0) r = mid;
                else if (flag > 0) l = mid + 1;
            }
            cnt[l]++;
        }
        for (int i = 0; i <= n; i++) printf("%d: %d\n", i, cnt[i]);
    }
    return 0;
}