POJ2318 TOYS

思路：二分。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 5005;
int n, m, x1, y1, x2, y2;

int box[maxn];

struct Board{
    int x1, x2;
} board[maxn];

bool onLeft(int idx, int x, int y){
    Board &b = board[idx];
    return (b.x2 - b.x1) * (y - y1) - (y2 - y1) * (x - b.x1) < 0;
}

int findPosition(int x, int y){
    int l = 0, r = n + 1;
    while(l + 1 != r){
        int mid = (l + r) >> 1;
        if (onLeft(mid, x, y))
            r = mid;
        else
            l = mid;
    }
    return l;
}

int main(){

    while(scanf("%d", &n) && n){
        memset(box, 0, sizeof(box));
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);

        board[0].x1 = board[0].x2 = x1;
        board[n+1].x1 = board[n+1].x2 = x2;
        for(int i = 1; i <= n; i++) scanf("%d%d", &board[i].x1, &board[i].x2);

        for(int i = 0; i < m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            int position = findPosition(x, y);
            box[position]++;
        }

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

    }
    return 0;
}

POJ2398 Toy Storage

思路：同上，记得给挡板排序。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 5005;
int n, m, x1, y1, x2, y2;

int box[maxn];

struct Cnt{
    int cnt, idx;
} cnt[maxn];

struct Board{
    int x1, x2;
} board[maxn];

bool onLeft(int idx, int x, int y){
    Board &b = board[idx];
    return (b.x2 - b.x1) * (y - y1) - (y2 - y1) * (x - b.x1) < 0;
}

int findPosition(int x, int y){
    int l = 0, r = n + 1;
    while(l + 1 != r){
        int mid = (l + r) >> 1;
        if (onLeft(mid, x, y))
            r = mid;
        else
            l = mid;
    }
    return l;
}

bool cmpBoard(const Board& b1, const Board& b2){
    if(b1.x1 == b2.x1)
        return b1.x2 < b2.x2;
    return b1.x1 < b2.x1;
}

int main(){
    while(scanf("%d", &n) && n){
        memset(box, 0, sizeof(box));
        memset(cnt, 0, sizeof(cnt));
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);

        board[0].x1 = board[0].x2 = x1;
        board[n+1].x1 = board[n+1].x2 = x2;
        for(int i = 1; i <= n; i++) scanf("%d%d", &board[i].x1, &board[i].x2);
        sort(board, board + n + 2, cmpBoard);

        for(int i = 0; i < m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            int position = findPosition(x, y);
            box[position]++;
        }

        for(int i = 0; i <= n; i++){
            cnt[box[i]].cnt++;
        }

        printf("Box\n");
        for(int i = 1; i <= m; i++)
            if(cnt[i].cnt)
                printf("%d: %d\n", i, cnt[i].cnt);

    }
    return 0;
}