计算几何的两道题

1.题意，给定三角形的三个点A,B,C的坐标。D,E,F,分别为三角形三个角的三等分线的交点，让你求出这三个点。

思路：求交点，则只要求两条直线的相关参数带入板子就可以了。这里关键是如何求解两条直线。由于三个点已知，所以这里关键在于求出三条直线的方向向量。三个点已知，则三角形的三条边已知，可以带入求两条直线夹角的板子，求出三角形的三个角，然后再除以3，就可以得到三个旋转角，分别把三角形三条边逆时针或顺时针旋转就可以的到三条直线的方向向量。然后就可以求交点了。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

struct Point{
    int x,y;
    Point(double x=0,double y=0):x(x),y(y){};
};   //定义一个点 

typedef Point V;      //定义一个向量 

V operator + (V A,V B) //定义两个向量的加法 
{
    return V(A.x+B.x,A.y+B.y);
}

V operator - (V A,V B) //定义两个向量的减法 
{
    return V(A.x-B.x,A.y-B.y);
}

V operator * (V A,double p) //定义一个向量与一个数的点乘 
{
    return V(A.x*p,A.y*p);
}

V operator / (V A,double p) //定义一个向量与一个数的除法 
{
    return V(A.x/p,A.y/p);
} 

bool operator < (const Point& a,const Point& b) //比较两个点的大小，先按x比较，再按y比较 
{
  return a.x<b.x||(a.x==b.x&&a.y<b.y);    
} 

const double eps=1e-10;

int dcmp(double x)
{
   if(fabs(x)<eps) return 0;
   else return x<0 ? -1 :1;      
} 

bool operator == (const Point& a,const Point& b) //比较两个点是否相等 
{
    return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; //如果 两个点的某个分量相等返回0，若前一个分量大于后一个分量返回-1，小于返回1； 
}
 
double Dot(V A,V B)  //计算两个向量的点积 
{
    return A.x*B.x+A.y*B.y;
}

double Length(V A)  //计算向量的长度 
{
    return sqrt(Dot(A,A));
}

double Angle(V A,V B)  //计算向量A,B的夹角 
{
    return acos(Dot(A,B)/Length(A)/Length(B));
} 

double Cross(V A, V B)  //计算两个向量的叉积 
{
    return  A.x*B.y-A.y*B.x;
} 

V Rotate(V A,double rad) //将A向量逆时针旋转rad弧度所得的新向量 
{
    return V(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));    
} 

Point GetlineIntersection(Point P,V v,Point Q,V w)//求出两条直线的交点
{                                                 // P是第一条直线的某个交点，v是第一条直线的方向向量 
    V u=P-Q;                                      // Q是第一条直线的某个交点，w是第一条直线的方向向量
    double t=Cross(w,u) / Cross(v,w);
    return P+v*t;
}

Point read_Point()
{
    double x,y;
    scanf("%lf%lf",&x,&y);
    return Point(x,y);
}

Point getD(Point A,Point B,Point C)
{
    V v1=C-B;
    double a=Angle(v1,A-B);
    v1=Rotate(v1,a/3);
    
    V v2=B-C;
    double b=Angle(v2,A-C);
    v2=Rotate(v2,-b/3);
    
    GetlineIntersection(B,v1,C,v2);
}

int T; 

int main()
{
    Point A,B,C,D,E,F;
    scanf("%d",&T);
    while(T--)
    {
        A=read_Point();
        B=read_Point();
        C=read_Point();
        D=getD(A,B,C);
        F=getD(C,A,B);
        E=getD(B,C,A);
        
        printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n",D.x,D.y,E.x,E.y,F.x,F.y);
    }

    return 0;
}

2.题意：平面上有一个包含n个顶点的一笔画，第n个顶点和第一个顶点重合，问这些线段可以把平面分为几个区域。

思路：emm思路嘛，直接给了一个公式分割区域数=边数+2-顶点数。咋得来的不知道。然后问题就转化为了，求这个一笔画有多少顶点数，和线段数了。顶点数分为两部分：原来的顶点+相交得到的顶点。

相交的顶点怎么算啦，可以先固定每一条线段，然后计算一笔画中剩下的线段中（显而易见的线段）与这条线段的交点，最后再用unique函数去重就可以算出不重复的点数（有的点可能会计算两次）。

线段数也分为两部分：原来的n条线段+相交的点重新分割每一条线段的到的新的线段关键是新的线段怎么计算啦，因为新的线段一定是，相交的点落在原有的线段上重新分割出来的，所以我们就计算所有点中有多少点落在了线段中间（不包含端点）最后就可以计算出线段数了

不看书我还真想不出来。

秒客网

计算几何的两道题

相关文章