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