计算几何 模板

（更新中。。。。。。。）

点 结构

struct point
{
    double x;//或为double
    double y;
}

浮点处理：

 int dbcmp(double x)
2 {
3     if(fabs(x) < eps) return 0;
4 
5     if(x < 0 ) return -1;
6     else  return  1;
7 }

点乘：

int betweencmp(point c,point a,point b)// c 是否在a ，b 间
 {
     return dbcmp(dot(c,a,b)) ;
 }

double dotdet(double x1,double y1,double x2,double y2)
 {
      return x1*x2+y1*y2 ;
 }
 double dot(point a,point b,point c)
 {
    return  dotdet(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
 }

叉积：

 double  det(double x1,double y1,double x2,double y2)
2  {
3      return x1*y2 - x2*y1;
4  }
5  double  cross(point a,point b,point c)
6  {
7      return det(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
8  }

 多边形的面积：

 1 double area(point p[])
 2 {
    注意 p[]中的点按 顺时针或逆时针 排 ，一般按 逆时针

    double s = 0;
 4     p[n].x = p[0].x;//以 （0，0） 为 跟点 ，也可以多边形边点为 跟点（利用 有向面积 的和）
 5     p[n].y = p[0].y ;
 6     for(int i = 0; i<n;i++)
 7     {
 8         s+=det(p[i].x,p[i].y,p[i+1].x,p[i+1].y);
 9 
10     }
11 
12     return fabs(s*0.5);
13 }

 

线段和线段的交点

point get (point a,point b,point c,point d)
 {
     point q;
     double s1, s2,s3,s4;
     int d1,d2,d3,d4;



     d1 = dbcmp(s1 = cross(a,b,c));
     d2 = dbcmp(s2 = cross(a,b,d));
     d3 = dbcmp(s3 = cross(c,d,a));
     d4 = dbcmp(s4 = cross(c,d,b));


     if((d1^d2) == -2 &&(d3^d4) == -2)//规范相交
     {

         q.x  = (c.x*s2 - d.x*s1)/(s2 - s1) ;// 求 交点 的 x 坐标
         q.y  = (c.y*s2 - d.y*s1)/(s2 - s1) ;// 求 交点 的 y 坐标

         return q ;
     }

     if(d1 == 0 && betweencmp(c,a,b) <= 0 ||         //非规范相交
        d2 == 0 && betweencmp(d,a,b) <= 0 ||
        d3 == 0 && betweencmp(a,c,d) <= 0 ||
        d4 == 0 && betweencmp(b,c,d) <= 0
        )
        {

             q.x  = (c.x*s2 - d.x*s1)/(s2 - s1) ;// 求 交点 的 x 坐标
             q.y  = (c.y*s2 - d.y*s1)/(s2 - s1) ;// 求 交点 的 y 坐标
             return q ;
        }



 }

直线和线段的交点 

 double getxy(point a,point b,point c,point d)//  a,b 代表直线 ，c,d 代表 线段
2 {
     // 判断是否相交 用 叉积 就可以了

     double s1 = cross(a,b,c);
4     double s2 = cross(a,b,d);
5 
6     x =  (c.x*s2 - d.x*s1)/(s2 - s1) ;// 求 交点 的 x 坐标
7     y =  (c.y*s2 - d.y*s1)/(s2 - s1) ;// 求 交点 的 y 坐标
8 }

 凸包 graham法：

int cmp(point a,point b)
{
    if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

void graham()
{

    int  i,len;
    top = 0;
    sort(p,p+n,cmp);

    if(n == 0) return ;
    if(n == 1) return ;
    stack[top++] = p[0];//stack[] 为 point 栈
    stack[top++] = p[1];
    for(i = 2 ;i<n;i++)//求右链
    {
        while(top > 1&& cross(stack[top - 1],stack[top - 2],p[i]) >= 0) top--;  //  >= 0 这 改为 > 0 可以 不去除  共线点    //注意 top 要 > 1

        stack[top++] = p[i];
    }

     //dblcmp(cross(p[stack[top - 1]],p[stack[top - 2]],p[i])) 可以直接是 cross
    len =  top ;

    for(i = n - 2;i >= 0;i--)//求左链
    {
         while(top > len && cross(stack[top - 1],stack[top - 2],p[i]) >= 0)top--;
         stack[top++] = p[i];

    }
    top--;//第一个点入栈两次 所以 减 1

}