题目连接: http://poj.org/problem?id=2318     http://poj.org/problem?id=2398

两题类似的题目,2398是2318的升级版。

题目大概是说,有一个矩形的柜子,中间有一些隔板。告诉你每个隔板的坐标,还有一些玩具的坐标,统计玩具在哪个格子里。

这题的思路很简单,如果玩具在某个隔板的左边和右边叉乘的正负是不同的。如图:

图中点P在线段CD的左边,则向量PC和向量PD叉乘结果小于0。反之P在AB的左边,向量PA叉乘PB大于0。

因此利用这个性质以及排序好的线段列表,通过二分思想,可以快速知道点在哪个格子内。

代码:

 #include<stdio.h>
#include<math.h>
#define PI 3.14159265358979323846
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define ABS(x) (((x)>0)?(x):(-(x)))
#define SIGN(x) (((x)<0)?-1:1)
#define EPS 0.000001/*精度控制*/
#define N 5005
/*坐标的定义*/
typedef double coo;/*int*/
/*点、向量*/
typedef struct POINT
{
coo x,y;
}point,vector;
/*线段*/
typedef struct SEGMENT
{
point p1,p2;/*p[2];*/
}segment;
/*判相等*/
int is_equel(double a,double b)
{
double c=ABS(a-b);
if(c<=EPS) return ;/*相等*/
else return ;/*不相等*/
}
/*向量的减法p1-p2*/
vector vector_minus(vector p1,vector p2)
{
vector p;
p.x=p1.x-p2.x;
p.y=p1.y-p2.y;
return p;
}
/*向量叉乘*/
double cross_product(vector p1,vector p2)
{/*x1y2-x2y1*/
return p1.x*p2.y-p1.y*p2.x;
}
int bijiao(segment s1,segment s2)/*比较两个线段的位置< */
{
if(s1.p1.x<s2.p1.x) return ;
if(s1.p1.x==s2.p1.x&&s1.p2.x<s2.p2.x) return ;
return ;
}
int Partition(segment r[],int low,int high)/*升序*/
/*返回支点最终位置*/
{
segment x;/*类型具体*/
if(low>high) return ;
if(low==high) return low;
x=r[low];
while(low<high)
{
while(low<high&&bijiao(x,r[high])) high--; /*<*/
if(low<high){r[low]=r[high];low++;}
while(low<high&&bijiao(r[low],x)) low++; /*>*/
if(low<high){r[high]=r[low];high--;}
}
r[low]=x;
return low;
}
void Quick_sort(segment r[],int m,int n) /*排序从r[m]到r[n]*/
{
int i;
if(m>=n) return;
i=Partition(r,m,n);
Quick_sort(r,m,i-);
Quick_sort(r,i+,n);
} int BinSearch(segment a[],int n,point k)/*在有序的数组a[0]~a[n-1]中查找k元素*/
{
int low=,high=n-,mid;
while(low<=high)
{
mid=low+((high-low)/);
if(cross_product(vector_minus(a[mid].p1,k),vector_minus(a[mid].p2,k))<) high=mid-;/*线段在右边*/
else low=mid+;
}
if(low>high) return high;
}
int main()
{
int n,m,i,a[N],b[N];
double x1,x2,y1,y2;
point p;
segment s[N];
while()
{
scanf("%d",&n);
if(n==) break;
scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);
s[].p1.x=x1;
s[].p1.y=y1;
s[].p2.x=x1;
s[].p2.y=y2;
for(i=;i<=n;i++)
{
scanf("%lf%lf",&s[i].p1.x,&s[i].p2.x);
s[i].p1.y=y1;
s[i].p2.y=y2;
}
s[i].p1.x=x2;
s[i].p1.y=y1;
s[i].p2.x=x2;
s[i].p2.y=y2;
Quick_sort(s,,n+);
for(i=;i<N;i++) a[i]=;
for(i=;i<m;i++)
{
scanf("%lf%lf",&p.x,&p.y);
a[BinSearch(s,n+,p)]++;
}
for(i=;i<N;i++) b[i]=;
for(i=;i<N;i++) b[a[i]]++;
printf("Box\n");
for(i=;i<N;i++) if(b[i]) printf("%d: %d\n",i,b[i]);
}
return ;
}

PKU 2398

最新文章

  1. druid配置数据库连接使用密文密码
  2. 【PHP夯实基础系列】PHP日期,文件系统等知识点
  3. iOS学习32之UIKit框架-可视化编程-XIB
  4. IIS-Server is too busy _解决方法
  5. JavaScript知识架构学习路径(一)- 变量篇
  6. qunit.js初试
  7. Oracle数据库启动时:ORA-00119: invalid specification for system parameter LOCAL_LISTENER; ORA-00132错误解决
  8. bzoj3130
  9. Python简易爬虫
  10. WPF按钮清空自带样式,以及透明按钮时,Grid的Background属性设置引起&quot;点击&quot;问题.
  11. loadRunner 11.0 安装及破解
  12. 使用sklearn进行数据挖掘-房价预测(4)—数据预处理
  13. C++几个技巧:智能指针在消息传递中的使用,元组,及lambda删除器
  14. LVS-DR模式(原理图详解)
  15. Dynamics CRM 非声明验证方式下连接组织服务的两种方式的性能测试
  16. python文件操作r+,w+,a+,rb+,
  17. [Machine Learning][The Analytics Edge][Predicting Earnings from Census Data]
  18. python 全栈开发,Day64(视图,触发器,函数,存储过程,事务)
  19. ubuntu + samba 共享失败
  20. linux下的进程信息管理

热门文章

  1. java基础知识回顾之final
  2. App接口设计思路
  3. bat批处理延迟运行脚本(zz)
  4. hdu 4061 A Card Game
  5. Android核心分析之十八Android电话系统之RIL-Java
  6. iOS App 唤醒另一个App
  7. 在CentOS下面编译WizNote Qt Project
  8. Difference between Pragma and Cache-control headers?
  9. uses-permission权限列表
  10. [转]matlab如何复制spectrum scope的图