1
#include<stdio.h>
2#include<math.h>
3
4const double eps=1e-6;
5
6//点(x,y)
7typedef struct
8
{
9
double x,y;
10
} Point;
11
12//直线方程ax+by+c=0
13typedef struct
14{
15 double a,b,c;
16} Line;
17
18//圆的标准方程(x-center.x)^2+(y-center.y)^2=r^2
19typedef struct
20{
21 Point center;
22 double r;
23} Circle;
24
25//浮点数符号函数
26int DblCmp(double d)
27{
28 if(fabs(d)<eps) return 0;
29 else return d>0?1:-1;
30}
31
32//线段AB的中点C
33Point MidPoint(Point A,Point B)
34{
35 Point C;
36 C.x=(A.x+B.x)/2;
37 C.y=(A.y+B.y)/2;
38 return C;
39}
40
41//点A到点B的距离
42double Dist(Point A,Point B)
43{
44 return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
45}
46
47//∠ACB的弧度值
48double Angle(Point A,Point B,Point C)
49{
50 double a,b,c;
51 a=Dist(B,C);
52 b=Dist(A,C);
53 c=Dist(A,B);
54 return acos((a*a+b*b-c*c)/(2*a*b));
55}
56
57//二维向量a=(x1,y1)与b=(x2,y2)的叉积的数值
58double Det(double x1,double y1,double x2,double y2)
59{
60 return x1*y2-x2*y1;
61}
62
63//二维向量的叉积AB*AC的数值
64double Cross(Point A,Point B,Point C)
65{
66 return Det(B.x-A.x,B.y-A.y,C.x-A.x,C.y-A.y);
67}
68
69//二维向量a=(x1,y1)与b=(x2,y2)的点积
70double DotDet(double x1,double y1,double x2,double y2)
71{
72 return x1*x2+y1*y2;
73}
74
75//二维向量的点积AB·AC
76double Dot(Point A,Point B,Point C)
77{
78 return DotDet(B.x-A.x,B.y-A.y,C.x-A.x,C.y-A.y);
79}
80
81//点A与B或C重合时为0,点A在BC内部时为-1,点A在BC外部时为1
82int BetweenCmp(Point A,Point B,Point C)
83{
84 return DblCmp(Dot(A,B,C));
85}
86
87//线段AB,CD规范相交则返回1,并求交点P;不规范相交则返回2;没有交点则返回0
88int SegsCross(Point A,Point B,Point C,Point D,Point &P)
89{
90 double s1,s2,s3,s4;
91 int d1,d2,d3,d4;
92 d1=DblCmp(s1=Cross(A,B,C));
93 d2=DblCmp(s2=Cross(A,B,D));
94 d3=DblCmp(s3=Cross(C,D,A));
95 d4=DblCmp(s4=Cross(C,D,B));
96 if(((d1^d2)==-2)&&((d3^d4)==-2))
97
{
98 P.x=(C.x*s2-D.x*s1)/(s2-s1);
99 P.y=(C.y*s2-D.y*s1)/(s2-s1);
100 return 1;
101
}
102 if(((d1==0)&&(BetweenCmp(C,A,B)<=0))||
103 ((d2==0)&&(BetweenCmp(D,A,B)<=0))||
104 ((d3==0)&&(BetweenCmp(A,C,D)<=0))||
105 ((d4==0)&&(BetweenCmp(B,C,D)<=0)))
106 return 2;
107 else return 0;
108}
109
110//直线L1,L2相交则返回1,并求交点P;重合则返回2,平行则返回0;
111int LinesCross(Line L1,Line L2,Point &P)
112{
113 double d1=Det(L1.a,L1.b,L2.a,L2.b),d2=Det(L1.b,L1.c,L2.b,L2.c),d3=Det(L1.a,L1.c,L2.a,L2.c);
114 int x=DblCmp(d1),y=DblCmp(d2);
115 if(x==0&&y==0) return 2;
116 else if(x==0&&y!=0) return 0;
117 else
118 {
119 P.x=d2/d1;
120 P.y=-d3/d1;
121 return 1;
122 }
123}
124
125//两点式:AB构造直线L
126Line LineFromSegs(Point A,Point B)
127{
128 Line L;
129 L.a=B.y-A.y;
130 L.b=A.x-B.x;
131 L.c=B.x*A.y-A.x*B.y;
132 return L;
133}
134
135//点斜式:A及方位向量dir构造直线L
136Line LineFromPointAndSlope(Point A,Point dir)
137{
138 Line L;
139 if(dir.x==0)
140 {
141 L.a=1;
142 L.b=0;
143 L.c=-A.x;
144 }
145 else
146 {
147 double k=dir.y/dir.x;
148 L.a=k;
149 L.b=-1;
150 L.c=A.y-k*A.x;
151 }
152 return L;
153}
154
155//两点A,B构造垂直平分线L
156Line PerbisecFromSegs(Point A,Point B)
157{
158 Line AB=LineFromSegs(A,B),L;
159 Point C=MidPoint(A,B),dir;
160 dir.x=B.y-A.y;dir.y=A.x-B.x;
161 L=LineFromPointAndSlope(C,dir);
162 return L;
163}
164
165//三点A,B,C构造圆O
166Circle CirFromPoints(Point A,Point B,Point C)
167{
168 Circle O;
169 double c=Dist(A,B),ACB=Angle(A,B,C);
170 O.r=c/(2*sin(ACB));
171 Line DO=PerbisecFromSegs(A,B),EO=PerbisecFromSegs(B,C);
172 Point P;
173 if(LinesCross(DO,EO,P)==1) O.center=P;
174 return O;
175}
posted on 2009-04-14 10:58
姚冰 阅读(450)
评论(0) 编辑 收藏 引用