题意：有一个抽屉，放入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;
}
