题意:有一个抽屉,放入n块按照x轴排序的不相交的隔板,分成n+1块区域,然后在给出m个玩具,统计每个区域的玩具个数。

数据解释:

n代表隔板数目,m是玩具数目,x1,y1是抽屉左上角坐标,x2,y2是抽屉右下角坐标。

接下来给出n块板子的顶部x坐标ui,底部x坐标li。

接下来给出m个玩具的坐标xi, yi。


题解:由于线段已经排序并且不相交,所以直接二分判断每个玩具坐标点处于直线的左右侧即可。


POJ2398是2318的强化版(感觉没强到哪去。。。),题意基本一样,就是隔板没有排序,所以要自己排序,并且输出的是按总数的个数升序输出。



代码:

poj 2318

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=5005;
const double eps=1e-12;
struct Point{
    double x, y;
    Point(double x=0, double y=0):x(x),y(y){}
};
struct Line{
    Point s, e;
    Line(){}
    Line(Point s, Point e):s(s), e(e){}
};
typedef Point Vector;
Vector operator +(Vector A, Vector B){return Vector(A.x+B.x, A.y+B.y);}
Vector operator -(Point A, Point B){return Vector(A.x-B.x, A.y-B.y);}
Vector operator *(Vector A, double p){return Vector(A.x*p, A.y*p);}
Vector operator /(Vector A, double p){return Vector(A.x/p, A.y/p);}
int dcmp(double x){
    if(fabs(x)<eps)return 0;else return x<0?-1:1;
}
double Cross(Vector A, Vector B){return A.x*B.y-A.y*B.x;}
double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);}
int n, m, x1, y1, x2, y2;
Line line[maxn];
Point point[maxn];
int cnt[maxn];
bool check(Point p, Line l){    //点是否在线的左边
    if(Area2(l.e, l.s, p)>=0)return 1;
    return 0;
}
int Find(Point p){
    int l=0, r=n;
    while(l<r){
        int mid=(l+r)/2;
        if(check(p, line[mid]))r=mid;
        else l=mid+1;
    }
    return l;
}
int main()
{
    while(~scanf("%d", &n)&&n){
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        double xi, yi, ui, li;
        memset(cnt, 0, sizeof(cnt));
        for(int i=0;i<n;i++){
            scanf("%lf%lf", &ui, &li);
            line[i].s=Point(ui, y1);
            line[i].e=Point(li, y2);
        }
        for(int i=0;i<m;i++){
            scanf("%lf%lf", &xi, &yi);
            int pos=Find(Point(xi, yi));
            cnt[pos]++;
        }
        for(int i=0;i<=n;i++){
            printf("%d: %d\n", i, cnt[i]);
        }
        puts("");
    }
    return 0;
}



POJ2398

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=5005;
const double eps=1e-12;
struct Point{
    double x, y;
    Point(double x=0, double y=0):x(x),y(y){}
};
struct Line{
    Point s, e;
    Line(){}
    Line(Point s, Point e):s(s), e(e){}
    bool operator <(const Line &cmp)const {
        return s.x<cmp.s.x;
    }
};
typedef Point Vector;
Vector operator +(Vector A, Vector B){return Vector(A.x+B.x, A.y+B.y);}
Vector operator -(Point A, Point B){return Vector(A.x-B.x, A.y-B.y);}
Vector operator *(Vector A, double p){return Vector(A.x*p, A.y*p);}
Vector operator /(Vector A, double p){return Vector(A.x/p, A.y/p);}
int dcmp(double x){
    if(fabs(x)<eps)return 0;else return x<0?-1:1;
}
double Cross(Vector A, Vector B){return A.x*B.y-A.y*B.x;}
double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);}
int n, m, x1, y1, x2, y2;
Line line[maxn];
Point point[maxn];
int cnt[maxn];
bool check(Point p, Line l){    //点是否在线的左边
    if(Area2(l.e, l.s, p)>=0)return 1;
    return 0;
}
int Find(Point p){
    int l=0, r=n;
    while(l<r){
        int mid=(l+r)/2;
        if(check(p, line[mid]))r=mid;
        else l=mid+1;
    }
    return l;
}
int main()
{
    while(~scanf("%d", &n)&&n){
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        double xi, yi, ui, li;
        memset(cnt, 0, sizeof(cnt));
        for(int i=0;i<n;i++){
            scanf("%lf%lf", &ui, &li);
            line[i].s=Point(ui, y1);
            line[i].e=Point(li, y2);
        }
        sort(line, line+n);
        for(int i=0;i<m;i++){
            scanf("%lf%lf", &xi, &yi);
            int pos=Find(Point(xi, yi));
            cnt[pos]++;
        }
        sort(cnt, cnt+n+1);
        puts("Box");
        cnt[n+1]=m+1;
        int tc=0;
        for(int i=0;i<=n;i++){
            if(cnt[i]){
                tc++;
                if(cnt[i]==cnt[i+1])continue;
                else{
                    printf("%d: %d\n", cnt[i], tc);
                    tc=0;
                }
            }
        }
    }
    return 0;
}