【POJ-2398】Toy Storage【还是叉积判三点旋向】

【POJ-2398】Toy Storage【还是叉积判三点旋向】

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

Solution:

【POJ-2318】TOYS【叉积判定三点旋向】处理方法完全相同,把那个结果的数组再重新用另外一个数组当做桶来处理一下,就可以了。需要注意的是,这道题给出的分隔板不再是从左到右顺序给出的,需要预先排序。

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

using namespace std;

const int LIM = 1000 + 10;
struct node {
    int xs, xe;
    bool operator < (const node &n) const {
        return xs < n.xs;
    }
};
int ans[LIM];
node x[LIM];
int cnt[LIM];

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++) {
        printf("Box\n");
        memset(cnt, 0, sizeof cnt);
        memset(ans, 0, sizeof ans);
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &x[i].xs, &x[i].xe);
        }
        sort(x, x + n);
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &a, &b);
            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                int flag = cross(a - x[mid].xe, b - y2, x[mid].xs - x[mid].xe, y1 - y2);
                if (flag < 0) r = mid;
                else if (flag > 0) l = mid + 1;
            }
            cnt[l]++;
        }
        for (int i = 0; i <= n; i++) ans[cnt[i]]++;
        for (int i = 1; i <= m; i++)
            if (ans[i]) printf("%d: %d\n", i, ans[i]);
    }
    return 0;
}