计算几何模板

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 #define LD double
 7 #define sqr(x) ((x)*(x))
 8 #define eps 1e-8
 9 #define INF 1e50
10 
11 using namespace std;
12 
13 /*
14 +：向量+ 
15 -：向量-
16 *：向量的数乘 ，点积
17 ^: 向量的叉积 
18 */
19 
20 struct node{    //点，向量 
21     LD x,y;
22     void scan(){scanf("%lf%lf",&x,&y);}        //输入输出 
23     void print(){printf("(%lf,%lf)
",x,y);}
24     node operator+(const node &a)const{return (node){x+a.x,y+a.y};} 
25     node operator-(const node &a)const{return (node){x-a.x,y-a.y};}
26     node operator*(const LD &a)const{return (node){x*a,y*a};}
27     node operator/(const LD &a)const{return (node){x/a,y/a};}
28     LD operator^(const node &a){return x*a.y-y*a.x;}
29     LD operator*(const node &a){return x*a.x+y*a.y;}
30     void operator+=(const node &a){*this=*this+a;}
31     void operator-=(const node &a){*this=*this-a;}
32     void operator*=(const LD &a){*this=(*this)*a;}
33     void operator/=(const LD &a){*this=*this/a;}
34     LD len(){return (LD)sqrt(sqr(x)+sqr(y));}    //向量的模长 
35     bool operator<(const node &a)const{        //大小比较(用于map) 
36         if(x==a.x) return y<a.y;
37         return x<a.x;
38     }
39 };
40 
41 LD dist(node a,node b){        //求点a，b距离 
42     return (a-b).len();
43 }
44 
45 struct line{    //线段（a，b） 
46     node a,b;
47     LD len(){return (a-b).len();}    //求线段长度 
48     void scan(){
49         a.scan();
50         b.scan();
51     }
52     void print(){    //输出线段 
53         puts("the Line is");
54         a.print();
55         b.print();
56     }
57 };
58 
59 node unit(node x){    //求向量x的单位向量 
60     LD tmp=x.len();
61     x/=tmp;
62     return x;
63 }
64 
65 bool crossing(line L1,line L2,node &point){        //求线段L1，L2的交点point，如果没有交点则返回false 
66     LD S1 = (L2.a-L2.b)^(L1.a-L2.b);
67     LD S2 = (L2.a-L2.b)^(L1.b-L2.b);
68     LD S3 = (L1.a-L1.b)^(L2.a-L1.b);
69     LD S4 = (L1.a-L1.b)^(L2.b-L1.b);
70     if(S1*S2>eps) return false;
71     if(S3*S4>eps) return false;
72     if(abs((L1.a-L1.b)^(L2.a-L2.b)) < eps) return false;
73     S1 = abs(S1);
74     S2 = abs(S2);
75     node v1=(L1.b-L1.a)*(S1/(S1+S2));
76     point=L1.a+v1;
77     return true;
78 }
基本模板
一个超级好用的函数atan2（y,x）返回原点到 (x,y) 的方位角度（α∈(-3.141592654,3.141592654]）。
用其进行极角排序。