poj 2318TOYS
2024-09-07 22:00:22
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;
}
通过叉积进行判断:
最新文章
- 使用蓝灯后,IE浏览器以及内置IE浏览器的程序不能使用的解决方案
- Some warning were found during validation
- 自定义cell自适应高度
- CodeVS 线段覆盖1~5
- js优化提升访问速度
- 不容易系列之(3)—— LELE的RPG难题
- web项目路径问题
- (转)Linux下tomcat JVM内存设置步骤
- Java语言基础(四) String和StringBuffer的区别
- C# ArrayList 基本用法 分类: C# 2014-09-26 11:03 524人阅读 评论(0) 收藏
- 从 Windows 到 Android: 威胁的持续迁移
- 最优秀的网络框架retrofit
- 使用Redis构建全局并发锁
- 内存管理-buddy[代码]
- 将lits集合转化为树状结构
- less的基本语法
- 初识Scala
- HDU2220 Eddy&#39;s AC难题
- python学习笔记之——unittest框架
- java时区转化相关工具方法
热门文章
- HP PROLIANT DL388 GEN10 (故障3019)SPP损坏
- Spring Cloud微服务Sentinel+Apollo限流、熔断实战总结
- kubernets之Deployment资源
- Array.of使用实例
- day128:MySQL进阶:
- Java多线程基础知识笔记(持续更新)
- MATLAB图像处理_Bayer图像处理 &; RGB Bayer Color分析
- Django--虛擬環境Virtualenv的安裝使用
- 前端面试之HTML5的新变化
- Crypto.getRandomValues()