首页 > 代码库 > poj 2318 TOYS & poj 2398 Toy Storage (叉积)
poj 2318 TOYS & poj 2398 Toy Storage (叉积)
链接:poj 2318
题意:有一个矩形盒子,盒子里有一些木块线段,并且这些线段坐标是按照顺序给出的,
有n条线段,把盒子分层了n+1个区域,然后有m个玩具,这m个玩具的坐标是已知的,问最后每个区域有多少个玩具
分析:从左往右,直到判断玩具是否在线段的逆时针方向为止,这个就需要用到叉积,当然可以用二分查找优化。
叉积:已知向量a(x1,y1),向量b(x2,y2),axb=x1*y2-x2*y1,
若axb>0,a在b的逆时针方向,若axb<0,则a在b的顺时针方向
注:每组数据后要多空一行
#include<stdio.h> #include<string.h> int chaji(int x1,int y1,int x2,int y2) { return x1*y2-x2*y1; } int main() { int u[5010],l[5010],x,y,x1,y1,x2,y2,m,n,i,j,s[5010]; while(scanf("%d",&n)!=EOF){ if(n==0) break; scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2); for(i=0;i<n;i++) scanf("%d%d",&u[i],&l[i]); u[n]=l[n]=x2; //将最后一个线段加上 memset(s,0,sizeof(s)); for(i=0;i<m;i++){ scanf("%d%d",&x,&y); for(j=0;j<=n;j++) if(chaji(u[j]-l[j],y1-y2,x-l[j],y-y2)>0){ //叉积判断 s[j]++; break; } } for(j=0;j<=n;j++) printf("%d: %d\n",j,s[j]); printf("\n"); } return 0; }
链接:poj 2398
意思与上题一样,只不过给出的线段乱序的,所以需要排序,
输出也有点不同,需要输出有玩具1-m个的区间有多少个,按顺序输出
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct point { int l,u; }p[1010]; int chaji(int x1,int y1,int x2,int y2) { return x1*y2-x2*y1; } int cmp(struct point a,struct point b) { if(a.l!=b.l) return a.l<b.l; return a.u<b.u; } int main() { int x,y,x1,y1,x2,y2,m,n,i,j,s[1010],a[1010]; while(scanf("%d",&n)!=EOF){ if(n==0) break; scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2); for(i=0;i<n;i++) scanf("%d%d",&p[i].u,&p[i].l); p[n].u=p[n].l=x2; sort(p,p+n+1,cmp); //对线段排序 memset(s,0,sizeof(s)); memset(a,0,sizeof(a)); for(i=0;i<m;i++){ scanf("%d%d",&x,&y); for(j=0;j<=n;j++) if(chaji(p[j].u-p[j].l,y1-y2,x-p[j].l,y-y2)>0){ s[j]++; break; } } for(j=0;j<=n;j++) a[s[j]]++; printf("Box\n"); for(i=1;i<=n;i++) if(a[i]) printf("%d: %d\n",i,a[i]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。