题目链接

题意

有一个矩形盒子，$n(n\leq 5e4)$条线段将其分成了$n+1$个区域（每条线段的两个端点分别在矩形的上边和下边，且线段互不相交）。现向盒子中扔$m(m\leq 5e4)$个玩具，问最终盒子的$n+1$个区域中各有多少玩具。数据保证玩具不会扔在线段上。

思路

假设玩具$P$在第$i$个区域，其左边为第$i$条线段$A_1B_1$，右边为第$i+1$条线段$A_2B_2$（$A$在上边，$B$在下边），则有$$\overrightarrow{PA_1}\times\overrightarrow{PB_1}\gt 0 且 \overrightarrow{PA_2}\times\overrightarrow{PB_2}\lt 0$$

并且左边的叉积都大于$0$，右边都小于$0$.

因此可以二分查找$P$的位置。

也可以先对玩具的横坐标用$lower\_bound$确定下来一个小范围，再在这个小范围内二分（直接查找也可以，因为这个范围应该很小）。

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 5010

int up[maxn], down[maxn], ans[maxn], n, m;

using namespace std;

typedef long long LL;

LL vec(LL x1, LL y1, LL x2, LL y2, LL x0, LL y0) {

    return (x1-x0) * (y2-y0) - (x2-x0) * (y1-y0);

}

void work() {

    memset(ans, 0, sizeof ans);

    int x1, y1, x2, y2;

    scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);

    for (int i = 1; i <= n; ++i) scanf("%d%d", &up[i], &down[i]);

    up[0] = down[0] = x1, up[n+1] = down[n+1] = x2;

    while (m--) {

        int x, y;

        scanf("%d%d", &x, &y);

        int p2 = lower_bound(down, down+n+1, x) - down,

            p1 = lower_bound(up, up+n+1, x) - up;

        if (p1 == p2) { ++ans[p1-1]; continue; }

        if (p1 > p2) swap(p1, p2);

        for (int i = p1; i <= p2; ++i) {

            if (vec(up[i], y1, down[i], y2, x, y) < 0) { ++ans[i-1]; break; }

        }

    }

    for (int i = 0; i <= n; ++i) printf("%d: %d\n", i, ans[i]);

    printf("\n");

}

int main() {

    while (scanf("%d", &n) && n) work();

    return 0;

}

巴特西

poj 2318 TOYS 点与矩形的关系

题目链接

题意

思路

Code

最新文章

热门文章