poj 2318(链接)

//第一发:莽写(利用ToLefttest)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std; struct Point{
int x,y;
}edge[5005],point[5005]; int a[5005]; bool ToLeft(int a,int b,int c,int d,int e,int f)
{
if((a*d+b*e+c*f-d*e-b*c-a*f)<0)return true;
else return false;
} int main ()
{
int n,m;
while(cin>>n,n)
{
cin>>m;
memset(a,0,sizeof(a));
cin>>edge[0].x>>edge[0].y>>point[0].x>>point[0].y;
for(int i=1;i<=n;i++)
cin>>edge[i].x>>edge[i].y;
for(int i=1;i<=m;i++)
cin>>point[i].x>>point[i].y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ToLeft(edge[i].x,edge[0].y,edge[i].y,point[0].y,point[j].x,point[j].y))
a[i]++;
for(int i=0;i<n;i++)
cout<<i<<':'<<' '<<a[i+1]-a[i]<<endl;
cout<<n<<':'<<' '<<m-a[n]<<endl<<endl;
}
return 0;
}

通过ToLefttest进行判断是否在每个箱子右边界的逆时针方向的左边;

#include<cstring >
#include<iostream>
using namespace std; //第二发:参考kuangbin(利用二分+叉积)
struct Point {
int x,y;
Point (){};
Point(int _x,int _y)
{
x=_x,y=_y;
}
Point operator -(const Point &b)const
{
return Point(x-b.x,y-b.y);
}
int operator *(const Point &b)const
{
return x*b.x+y*b.y;
}
int operator ^(const Point &b)const
{
return x*b.y-y*b.x;
}
}; struct Line{
Point s,e;
Line(){};
Line(Point _s,Point _e)
{
s=_s,e=_e;
}
}; int xmult(Point p0,Point p1,Point p2)//求P0p1和 p0p2 的叉积
{
return (p1-p0)^(p2-p0);
} const int MAXN=5050;
Line line[MAXN];
int ans[MAXN]; int main ()
{
int n,m,x1,y1,x2,y2;
while(cin>>n,n)
{
cin>>m>>x1>>y1>>x2>>y2;
int U,L;
for(int i=0;i<n;i++)
{
cin>>U>>L;
line[i]=Line(Point(U,y1),Point(L,y2));
}
line[n]=Line(Point(x2,y1),Point(x2,y2));
int x,y;
Point p;
memset(ans,0,sizeof(ans));
while(m--)
{
cin>>x>>y;
p=Point(x,y);
int l=0,r=n;
while(l<r)
{
int mid=(l+r)/2;
if(xmult(p,line[mid].e,line[mid].s)>0)
r=mid;
else
l=mid+1;
}
ans[l]++;
}
for(int i=0;i<=n;i++)
cout<<i<<": "<<ans[i]<<endl;
cout<<endl;
}
return 0;
}

通过叉积进行判断:

最新文章

  1. 使用蓝灯后,IE浏览器以及内置IE浏览器的程序不能使用的解决方案
  2. Some warning were found during validation
  3. 自定义cell自适应高度
  4. CodeVS 线段覆盖1~5
  5. js优化提升访问速度
  6. 不容易系列之(3)—— LELE的RPG难题
  7. web项目路径问题
  8. (转)Linux下tomcat JVM内存设置步骤
  9. Java语言基础(四) String和StringBuffer的区别
  10. C# ArrayList 基本用法 分类: C# 2014-09-26 11:03 524人阅读 评论(0) 收藏
  11. 从 Windows 到 Android: 威胁的持续迁移
  12. 最优秀的网络框架retrofit
  13. 使用Redis构建全局并发锁
  14. 内存管理-buddy[代码]
  15. 将lits集合转化为树状结构
  16. less的基本语法
  17. 初识Scala
  18. HDU2220 Eddy&#39;s AC难题
  19. python学习笔记之——unittest框架
  20. java时区转化相关工具方法

热门文章

  1. HP PROLIANT DL388 GEN10 (故障3019)SPP损坏
  2. Spring Cloud微服务Sentinel+Apollo限流、熔断实战总结
  3. kubernets之Deployment资源
  4. Array.of使用实例
  5. day128:MySQL进阶:
  6. Java多线程基础知识笔记(持续更新)
  7. MATLAB图像处理_Bayer图像处理 &amp; RGB Bayer Color分析
  8. Django--虛擬環境Virtualenv的安裝使用
  9. 前端面试之HTML5的新变化
  10. Crypto.getRandomValues()