首页 > 代码库 > UVA 11178

UVA 11178

问题描述:

给定三角形的三个点,求三角形角三平分线连成的内部小三角形的三个点的坐标

 

 
这里主要还是几何问题上的大量函数求解问题,
这题的关键是经过两点的确定直线的交点求解问题,我们总是可以利用叉积解决大量问题
通过叉积的比来得到那个方向的向量比例,最后得到点
  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cmath>  5 using namespace std;  6 //用来保证double的精度问题  7 #define eps 1e-10  8 const double PI = acos(-1);  9 struct Point { 10     double x, y; 11     Point(double x=0,double y=0):x(x),y(y){}//构造函数,方便代码编写 12 }; 13 typedef Point Vector; 14  15 bool operator==(const Point &a,const Point &b) 16 { 17     return abs(a.x-b.x)<eps && abs(a.y-b.y)<eps; 18 } 19  20 Vector operator-(Point a,Point b) 21 { 22     return Vector(a.x-b.x,a.y-b.y); 23 } 24  25 Vector operator+(Vector a,Vector b) 26 { 27     return Vector(b.x+a.x,b.y+a.y); 28 } 29  30 Vector operator*(Vector a,double b) 31 { 32     return Vector(a.x*b,a.y*b); 33 } 34  35 Vector operator/(Vector a,double b) 36 { 37     return Vector(a.x/b,a.y/b); 38 } 39  40  41 //两向量的内积 42 double Dot(Vector a,Vector b) 43 { 44     return a.x*b.x + a.y*b.y; 45 } 46  47 //两向量的叉积 48 double Cross(Vector a,Vector b) 49 { 50     return a.x*b.y - a.y*b.x; 51 } 52  53 //向量的长度 54 double length(Vector a) 55 { 56     return sqrt(Dot(a,a)); 57 } 58  59 //两向量的夹角弧度 60 double get_rad(Vector a,Vector b) 61 { 62     return acos((Dot(a,b))/length(a)/length(b)); 63 } 64  65 //求一个向量逆时针偏转一定弧度后得到的向量,若是顺时针,我们在弧度上加一个负号就行了 66 Vector get_revovle(Vector a,double rad) 67 { 68     double x = a.x*cos(rad) - a.y*sin(rad); 69     double y = a.x*sin(rad) + a.y*cos(rad); 70     return Vector(x,y); 71 } 72  73 //得到经过两个点的确定直线的交点 74 Point getLineIntersection(Point p,Vector vp,Point q,Vector vq) 75 { 76     Vector u = p-q; 77     double t = Cross(vq,u) / Cross(vp,vq); 78     return p+vp*t; 79 } 80  81 //这个函数求以a为顶点,b,c延伸出1/3弧度处的直线的交点 82 Point getIntersection(Point a,Point b,Point c) 83 { 84     Vector v1 = a-b; 85     Vector v2 = a-c; 86     Vector v3 = c-b; 87     Vector v4 = b-c; 88     double rad1 = get_rad(v1,v3); 89     double rad2 = get_rad(v2,v4); 90     rad1/=3; 91     rad2/=3; 92     Vector rev1 = get_revovle(v3,rad1); 93     Vector rev2 = get_revovle(v4,-rad2);//负数表示顺时针旋转 94  95     return getLineIntersection(b,rev1,c,rev2); 96 } 97  98 int main() 99 {100     int T;101     double x1,y1,x2,y2,x3,y3;102     scanf("%d",&T);103     while(T--){104         scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);105 106         Point A(x1,y1);107         Point B(x2,y2);108         Point C(x3,y3);109 110         Point ans1 = getIntersection(A,B,C);111         Point ans2 = getIntersection(B,C,A);112         Point ans3 = getIntersection(C,A,B);113 114         printf("%.6f %.6f %.6f %.6f %.6f %.6f\n",ans1.x,ans1.y,ans2.x,ans2.y,ans3.x,ans3.y);115     }116     return 0;117 }

 

UVA 11178