题目链接：http://poj.org/PRoblem?id=2398 题意：题意和poj 2318惊人的相似，只不过输出有点不一样，输出是指有多少个盒子含有那么多个玩具，比如样例一，含有两个玩具的盒子有两个。还有就是给出的挡板是没有排好序的 解析：把挡板排好序以后，就用叉乘判断玩具的位置即可,输出的时候稍微处理一下就好
#include <cmath>#include <algorithm>#include <iostream>#include <cstdio>#include <vector>#include <cstring>using namespace std;const int maxn = 1e5;const double eps = 1e-5;struct point{ int x,y; point() {} point(int _x,int _y) { x = _x; y = _y; }}b[maxn],c[maxn];struct line{ point a,b; bool Operator < (const line b)const { return a.x<b.a.x; }}a[maxn];int ans[maxn];struct node{ int id,num; bool operator < (const node &b)const { return id<b.id; }}vis[maxn];int cross(point p0,point p1,point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int dot_online(point t1,line l){ return cross(t1,l.a,l.b);}int main(void){ int n,m; while(~scanf("%d",&n)&&n) { point s,e; memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); scanf("%d %d %d %d %d",&m,&s.x,&s.y,&e.x,&e.y); int cnt = 0; a[cnt].a = s; a[cnt++].b = point(s.x,e.y); for(int i=0;i<n;i++) scanf("%d %d",&c[i].x,&c[i].y); for(int i=0;i<n;i++) { a[cnt].a = point(c[i].x,s.y); a[cnt++].b = point(c[i].y,e.y); } a[cnt].a = point(e.x,s.y); a[cnt++].b = e; sort(a,a+n+1); for(int i=0;i<m;i++) scanf("%d %d",&b[i].x,&b[i].y); for(int i=0;i<m;i++) { for(int j=0;j<=n;j++) { if(dot_online(b[i],a[j])>0 && dot_online(b[i],a[j+1])<0) { ans[j]++; break; } } } for(int j=0;j<=n;j++) { vis[ans[j]].num++; vis[ans[j]].id = ans[j]; } sort(vis,vis+m); puts("Box"); for(int i=0;i<=m;i++) { if(vis[i].id==0) continue; printf("%d: %d/n",vis[i].id,vis[i].num); } } return 0;}新闻热点
疑难解答
