计算几何(point&line)红书模板

Posted by Cww97 on 2017-08-20

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/77429602

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
const int MAXN = 1e6 + 5;
const double eps = 1e-8;

int cmp(double x) {
if(fabs(x) < eps) return 0;
if(x > 0) return 1;
return -1;
}

const double pi = acos(-1.0);
inline double sqr(double x) {
return x * x;
}
struct point{
double x, y;
point(){}
point(double a, double b) : x(a), y(b) {}
void input() {
scanf("%lf%lf", &x, &y);
}
friend point operator + (const point &a, const point &b) {
return point(a.x + b.x, a.y + b.y);
}
friend point operator - (const point &a, const point &b) {
return point(a.x - b.x, a.y - b.y);
}
friend bool operator == (const point &a, const point &b) {
return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0;
}
friend point operator * (const point &a, const double &b) {
return point(a.x * b, a.y * b);
}
friend point operator * (const double &a, const point &b) {
return point(a * b.x, a * b.y);
}
friend point operator / (const point &a, const double &b) {
return point(a.x / b, a.y / b);
}
double norm() {
return sqrt(sqr(x) + sqr(y));
}
};
double det(const point &a, const point &b) {
return a.x * b.y - a.y * b.x;
}
double dot(const point &a, const point &b) {
return a.x * b.x + a.y * b.y;
}
double dist(const point &a, const point &b) {
return (a - b).norm();
}
point rotate_point(const point &p, double A) {
double tx = p.x, ty = p.y;
return point(tx * cos(A) - ty * sin(A), tx * sin(A) + ty * cos(A));
}
struct line{
point a, b;
line(){}
line(point x, point y) : a(x), b(y){}
};
line point_make_line(const point a, const point b) {
return line(a, b);
}
double dis_point_segment(const point p, const point s, const point t) {
if(cmp(dot(p-s, t-s)) < 0) return (p - s).norm();
if(cmp(dot(p-t, s-t)) < 0) return (p - t).norm();
return fabs(det(s-p, t-p)/dist(s,t));
}
void PointProjLine(const point p,const point s, const point t,point &cp){
double r = dot((t-s), (p-s))/dot(t-s, t-s);
cp=s+r*(t-s);
}
bool PointOnSegment(point p, point s, point t){
return cmp(det(p-s, t-s))==0 && cmp(dot(p-s,p-t))<=0;
}
bool parallel(line a,line b){
return !cmp(det(a.a-a.b,b.a-b.b));
}
bool line_make_point(line a,line b,point &res){
if (parallel(a,b)) return false;
double s1=det(a.a-b.a,b.b-b.a);
double s2=det(a.b-b.a,b.b-b.a);
res=(s1*a.b-s2*a.a)/(s1-s2);
return true;
}
line move_d(line a, const double &len) {
point d = a.b - a.a;
d = d / d.norm();
d = rotate_point(d, pi/2);
return line(a.a + d*len, a.b + d * len);
}