poj 2398 Toy Storage (计算几何,判断点和线段关系)

http://poj.org/problem?id=2398

题意大概是说将一个盒子用n个board分成n+1 部分

然后往里面放toy,给定盒子,board,和toy的坐标

问所有的toy放完后,有多少部分中有t个toy;

简单计算几何

需要判断的是点和直线的关系.

判断 某一点在直线左右侧

左右方向是相对前进方向的,只要指定了前进方向就可以知道左右(比如指定前进方向是从直线的起点到终点).判断点在直线的左侧还是右侧是计算几何里面的一个最基本算法.使用矢量来判断. 
定义:平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量:


S(P1,P2,P3)=|y1 y2 y3|= (x1-x3)*(y2-y3)-(y1-y3)*(x2-x3) 

当P1P2P3逆时针时S为正的,当P1P2P3顺时针时S为负的。 

令矢量的起点为A,终点为B,判断的点为C, 
如果S(A,B,C)为正数,则C在矢量AB的左侧; 
如果S(A,B,C)为负数,则C在矢量AB的右侧; 
如果S(A,B,C)为0,则C在直线AB上。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz