1.精度
计算几何与解析几何、向量代数等都有一定的关系，用一定的数据结构与算法来处理几何问题。但是计算几何跟数学的解析几何解决问题的首选方法还是有比较大的区别。计算几何，首先要注意“计算”二字，一定要注意精度问题。在很多题目中，精度设置是直接影响AC还是WA的关键因素。因此，第一，如需要使用浮点数，一般使用double而不用float；第二，浮点数判零的方法，精度最直接体现在这里（工程实践中浮点数也是这样判零的，或者说计算机中浮点数就应该这样判零）。
double const EPS = 1E-6;
#define is0(x) ( -EPS <= (x) && (x) <= EPS )EPS的具体大小根据题意进行设置。在很多提交过程中，就是因为EPS设置不当而导致WA，与算法无关。既然精度是有可能导致WA的一个“非算法”因素，由此也确定了计算几何中的另外一条原则：尽量使用整数！！！使用整数，就可以不考虑精度问题，就可以完全只考虑算法问题。一般而言，绝大部分题目都会给出整点（也就是坐标为整数的点），这是整数解题的基础。而且有相当多的题目都存在整数型解法。只有少数题目输入是整点，但计算过程中必须使用浮点数。极少数题目从输入开始就必须使用浮点数。下面只说平面几何。计算几何最基本的数据结构就是点：
struct point_t{
int x;
int y;
};2.叉积点积
这个数据结构同时还可以表示向量，而计算几何中最常用的计算就是叉积，假设有2个三维向量p1、p2，坐标分别是(x1,y1,z1)、(x2,y2,z2)，则它们的叉积计算可使用行列式进行标记。
i
j
k
x1
y1
z1
x2
y2
z2
普遍使用的计算几何模板中，使用三个点计算叉积，代码如下：
//向量的叉积，表示OA×OB
int cross(point_t const&O,point_t const& A,point_t const& B){
int xoa = A.x – O.x;
int yoa = A.y – O.y;
int xob = B.x – O.x;
int yob = B.y – O.y;
return xoa * yob - yoa * xob;
}叉积是ACM计算几何最重要的判据，毫不夸张的说绝大部分解题过程都要用到叉积。而点积相对用的较少，点积隐含了两个向量夹角的余弦值。所以可做一个定性判断：点积为0，两向量垂直；为正，锐角；为负，钝角。仿照叉积，点积的实现如下：
//向量的点积，表示OA·OB
int dot(point_t const&O,point_t const& A,point_t const& B){
int xoa = A.x – O.x;int yoa = A.y – O.y;
int xob = B.x – O.x;
int yob = B.y – O.y;
return xoa * xob + yoa * yob;
}下面再举两个使用整数运算解决计算几何问题的例子（输入为整点）：判断两线段是否相交，判断两直线位置关系。 首先给出线段的数据结构，当然这个结构很多时候不一定会用到。
struct lineseg_t {
point_t s;
point_t e;
};两线段是否相交，需要经过快速排斥实验和跨立实验两个阶段的判断。所谓排斥实验是指如下图两个线段显然是不相交的。也就是说AB最大的x坐标还要比CD最小的x坐标小，那显然不相交。此类可能性共有4种。这个判断背后有一个简单的几何定理，两线段相交，则它们在任意直线上的投影必有重合部分；反过来，如果存在一条直线，两条线段在其上的投影不重合，则这两条线段不相交。排斥实验就是用x轴和y轴作为投影用的直线。 
bool isInter(point\_t const&A,point\_t const&B, point\_t const&C,point\_t const&D){
return max(A.x, B.x) >= min(C.x, D.x)
&& max(A.y, B.y) >= min(C.y, D.y)
&& max(C.x, D.x) >= min(A.x, B.x)
&& max(C.y, D.y) >= min(A.y, B.y)
&& cross(A, C, B) * cross(A, B, D) >= 0
&& cross(C, A, D) * cross(C, D, B) >= 0 ;
}前4个实现排斥实验，后2个实现跨立实验，很显然只要输入为整数，这个实现只用到了整数运算。下面考虑计算直线的位置关系（平面几何）。直线一般用如下数据结构表示：
struct line_t{
int a,b,c;//表示ax+by+c=0,一般使得a、b、c互质
}题目一般不会直接给出直线方程，而是通过2点确定一条直线，同样只要给定的是整点，就能很方便的确定整型的直线参数。仍然使用叉积，计算行列式如下：
a
b
c
x1
y1
1
x2
y2
1
很容易得到 a = y1 - y2, b = x2 - x1, c = x1y2 - x2y1。然后可以考虑求三者的最大公约数做一个归约（并非必须，有的题目这么做以后会方便处理，而有的题目完全不需要这么做）。给定2条直线，求其位置关系也可以使用叉积，计算行列式如下： 也很容易算到：x = b1c2 - b2c1, y = a2c1 - a1c2, t = a1b2 - a2b1。如果三者全为0，两直线重合；t为0，两直线平行；否则两直线相交且交点为(x/t, y/t)。很明显，上述过程中除了最后一步给出交点的具体坐标之外，其余运算全部是整数运算。 所以计算几何在条件允许的情况下，优先只用整数运算，而很多情况下的确可以做到这一点。总的来说，这个极大提高AC的机会，既避免精度问题，又避免了潜在的TLE（浮点运算以及三角函数、反三角函数显然比整数运算慢的多）。
