计算几何模板

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
//floor(x) 向下取整函数
//ceil(x)  向上取整函数
//round(x)  四舍五入函数
struct Point{
	double x,y;
	Point(double x=0,double y=0):x(x),y(y){} //构造函数，方便代码编写
};
typedef Point Vector;
//向量+向量=向量 向量+点=点
Vector operator + (Vector A,Vector B){
	return Vector(A.x+B.x,A.y+B.y);
}
//点-点=向量
Vector operator - (Point A,Point B){
	return Vector(A.x-B.x,A.y-B.y);
}
//向量*数=向量
Vector operator * (Vector A,double p){
	return Vector(A.x*p,A.y*p);
}
//向量/数=向量
Vector operator / (Vector A,double p){
	return Vector(A.x/p,A.y/p);
}
bool operator < (const Point& a,const Point& b){
	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;
}
//点积
double Dot(Vector A,Vector B){
	return A.x*B.x+A.y*B.y;
}
//向量长度
double Length(Vector A){
	return sqrt(Dot(A,A));
}
//向量夹角
double Angle(Vector A,Vector B){
	return acos(Dot(A,B)/Length(A)/Length(B));
}
//叉积：计算三角形有向面积的2倍（叉积cross(v,w)）w在v的左边叉积大于0，否则小于0 共线等于0
double Cross(Vector A,Vector B){
	return A.x*B.y-A.y*B.x;
}
//三点形成的面积
double Area2(Point A,Point B,Point C){
	return Cross(B-A,C-A);
}
//rad是弧度
Vector Rotate(Vector A,double rad){
	return (A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//计算向量的单位法向量
Vector Normal(Vector A){
	double L=Length(A);
	return Vector(-A.y/L,A.x/L);
}
//利用三角形相似得证俩个直线得交点
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){
	Vector u=P-Q;
	double t=Cross(w,u)/Cross(v,w);
	return P+v*t;
}
//点到直线得距离
double DistanceToLine(Point P,Point A,Point B){
	Vector v1=B-A,v2=P-A;
	return fabs(Cross(v1,v2))/Length(v1);//取绝对值是无向距离，不取有向距离
}
//点到线段得距离
double DistanceToSegment(Point P,Point A,Point B){
	if(A==B) return Length(P-A);
	Vector v1=A-B,v2=P-A,v3=P-B;
	if(dcmp(Dot(v1,v2))<0) return Length(v2);
	else if(dcmp(Dot(v1,v3))>0) return Length(v3);
	else return fabs(Cross(v1,v2))/Length(v1);
}
//求点P在直线A->B得投影
Point GetLineProjection(Point P,Point A,Point B){
	Vector v=B-A;
	return A+v*(Dot(v,P-A)/Dot(v,v));
}
//求俩线段是否相交(不包括端点)
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){
	double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
	double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
	return dcmp(c1)*dcmp(c2)<=0&&dcmp(c3)*dcmp(c4)<=0;
}
bool OnSegment(Point P,Point a1,Point a2){
	return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
}
int main(){

	return 0;
}