首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。