首页 > 代码库 > poj 2398 Toy Storage 【计算几何】【点和线的关系】
poj 2398 Toy Storage 【计算几何】【点和线的关系】
题目链接:http://poj.org/problem?id=2398
题目大意:这次的题目和前一道题目几乎是一样的,不同之处在于这次给出的线不是有顺序的,还有就是输出的时候有一个优化。
基本的分析见我上篇博客:http://blog.csdn.net/u010468553/article/details/39474007
注意sort函数中cmp的编写还有后期数据的整理
#include<iostream> #include<stdio.h> #include<cstring> #include<stdlib.h> #include<algorithm> using namespace std; struct point { double x;double y; point(const double &x = 0, const double &y = 0):x(x), y(y){} //注意最后两个字母别打错了 void in(){scanf("%lf%lf",&x,&y);} void out()const{ printf("%.2lf %.2lf\n",x,y);} }s,e; struct line{ point s; point e; }; int n,m; //n条线(分成n+1个区域) m个玩具 最后输出每个区域内的玩具个数 line L[5005]; point P; int cnt[5005]; //计算叉乘(P1-P0)X(P2-P0) double xmult(point p1,point p2,point p0){ return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x); } bool cmp(const line& l1, const line& l2) { if (min(l1.s.x, l1.e.x) == min(l2.s.x, l1.e.x)) return max(l1.s.x, l1.e.x) < max(l2.s.x, l1.e.x); return min(l1.s.x, l1.e.x) < min(l2.s.x, l1.e.x); } void B_search(point P){ int l=0,r=n-1,mid; while(l<r){ mid = (l+r)/2; if(xmult(P,L[mid].s,L[mid].e) > 0) l = mid + 1; else r = mid; } if(xmult(P,L[l].s,L[l].e)<0) cnt[l]++; else cnt[l+1]++; } int main () { while(~scanf("%d",&n)){ memset(cnt,0,sizeof(cnt)); if(n==0) break; scanf("%d %lf %lf %lf %lf",&m,&s.x,&s.y,&e.x,&e.y); for(int i=0;i<n;i++){ double t1,t2; scanf("%lf %lf",&t1,&t2); L[i].s.x=t1; L[i].s.y=s.y; L[i].e.x=t2; L[i].e.y=e.y; } sort(L, L+n, cmp); for(int i=0;i<m;i++){ scanf("%lf %lf",&P.x,&P.y); B_search(P); } int ans[5005]; memset(ans,0,sizeof(ans)); for(int i=0;i<=n;i++) ans[ cnt[i] ] ++ ; printf ("Box\n"); for (int i = 1; i <= m; i++) if (ans[i] != 0) { printf ("%d: %d\n", i, ans[i]); m -= i * cnt[i]; } } }
poj 2398 Toy Storage 【计算几何】【点和线的关系】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。