如题= =自用模板

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
class Line{    
    Point a;    
    Point b;    
    Line(double x1,double y1,double x2,double y2){    
        a=new Point(x1,y1);    
        b=new Point(x2,y2);    
    }    
    Line(Point a,Point b){    
        this.a=a;    
        this.b=b;    
    }    
}    
class Point{    
    double x;    
    double y;    
    Point(double x,double y){    
        this.x=x;    
        this.y=y;    
    }    
}    
class GeoMetry{    
    static double eps=1e-7;    
    Point sub(Point a, Point b){    
        Point t=new Point(0,0);t.x=a.x-b.x;t.y=a.y-b.y;    
        return t;    
    }    
    double cross(Point a,Point b){    
        return a.x*b.y-b.x*a.y;    
    }    
        
    //看转向    
    double turn(Point p1,Point p2,Point p3){    
        return cross(sub(p2,p1),sub(p3,p1));    
        }    
        
    //看两直线是否共线    
    boolean online(Line a,Line b){    
        if((Math.abs(turn(a.a,a.b,b.a))<eps)&&(Math.abs(turn(a.a,a.b,b.b))<eps))return true;   
        return false;    
    }    
        
    //看两直线是否平行    
    boolean par(Line a,Line b){    
        if(Math.abs(cross(sub(a.a,a.b),sub(b.a,b.b)))<eps)return true;    
        return false;    
    }  
        
    //求两直线交点    
    Point jiaodian(Line a,Line b){    
        double k1,k2,t;    
        k1=cross(sub(a.b,b.a),sub(b.b,b.a));    
        k2=cross(sub(b.b,b.a),sub(a.a,b.a));    
        t=k1/(k1+k2);    
        Point ans=new Point(0,0);    
        ans.x=a.b.x+(a.a.x-a.b.x)*t;    
        ans.y=a.b.y+(a.a.y-a.b.y)*t;    
        return ans;    
    }    
        
    //求多边形面积    
    double square(Point[]p){     
        double squ=0;    
        if(p.length<=2)return 0.0;    
        for(int i=1;i<p.length-1;i++){    
            squ+=cross(sub(p[i],p[0]),sub(p[(i+1)%p.length],p[0]));    
        }    
        return Math.abs(squ/2);    
    }    
    double disofPointAndPoint(Point a,Point b){  
        return Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));  
    }  
    double disofPointandLine(Point p,Line k){  
        Point[]q=new Point[3];  
        q[0]=p;  
        q[1]=k.a;  
        q[2]=k.b;  
        double s=square(q);  
        return s*2/Math.sqrt((k.a.x-k.b.x)*(k.a.x-k.b.x)+(k.a.y-k.b.y)*(k.a.y-k.b.y));  
    }  
    //求两点构成的直线的法线    
    Line ppline(Point a, Point b){    
        Line ret=new Line(new Point (0,0),new Point(0,0));    
        ret.a.x = (a.x+ b.x)/2;    
        ret.a.y = (a.y + b.y)/2;    
        //一般式    
        double reta =b.x - a.x;    
        double retb =b.y - a.y;    
        double retc = (a.y - b.y) * ret.a.y + (a.x - b.x) * ret.a.x;    
        if(Math.abs(reta) > eps){    
            ret.b.y = 0.0;    
            ret.b.x = - retc / reta;    
            if(Math.abs(ret.b.x-ret. a.x)<eps&&Math.abs(ret.b.y-ret.a.y)<eps){    
                ret.b.y = 1e10;    
                ret.b.x = - (retc - retb * ret.b.y) / reta;    
            }    
        }    
        else{    
            ret.b.x = 0.0;    
            ret.b.y = - retc / retb;    
            if(Math.abs(ret.b.x-ret. a.x)<eps&&Math.abs(ret.b.y-ret.a.y)<eps){    
                ret.b.x = 1e10;    
                ret.b.y = - (retc - reta * ret.b.x) / retb;    
            }    
        }    
        return ret;    
    }    
      
    //点在圆内  
    int ifPointInTheCircle(Point p,Point yuandian,double radius){ //in: 1 on:0 out:-1  
        double rr=(p.x-yuandian.x)*(p.x-yuandian.x)+(p.y-yuandian.y)*(p.y-yuandian.y);  
        double r2=radius*radius;  
        if(rr<r2){  
            return 1;  
        }else if(Math.abs(rr-r2)<eps){  
            return 0;  
        }else{  
            return -1;  
        }  
    }  
      
    //线段与圆是否相交  解方程法 u范围:0-1才有解 交点:x=x1+u*(x2-x1) y=y1+u(y2-y1)
    boolean ifSegmentIntersectCircle(Line l,Point yuandian,double radius){  
        double x1=l.a.x;  
        double y1=l.a.y;  
        double x2=l.b.x;  
        double y2=l.b.y;  
        double x3=yuandian.x;  
        double y3=yuandian.y;  
        double A=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);  
        double B=2*((x2-x1)*(x1-x3)+(y2-y1)*(y1-y3));  
        double C=x3*x3+y3*y3+x1*x1+y1*y1-2*(x3*x1+y3*y1)-radius*radius;  
        double judge=B*B-4*A*C;  
        if(judge<0)return false; //无交点  
        else if(cmp(judge,0)==0){  
            double u1=(-B)/(2*A);  
            if(cmp(u1,1)<=0&&cmp(u1,0)>=0)return true; //u需要在0-1 相切  
            else return false;  
        }else{  
            double u1=(-B+Math.sqrt(judge))/(2*A);  
            double u2=(-B-Math.sqrt(judge))/(2*A);  
            if(cmp(u1,1)<=0&&cmp(u1,0)>=0&&cmp(u2,0)>=0&&cmp(u2,1)<=0)return true; //两个交点  
            if(cmp(u1,1)<=0&&cmp(u1,0)>=0||cmp(u2,0)>=0&&cmp(u2,1)<=0)return true; //一个交点  
            else return false;  
        }  
          
    }
	
	//两圆重叠的面积
	double intersect(Point a,double r1,Point b,double r2){
		double dis=Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
		if(r1+r2<dis+eps)return 0;
		if(dis<Math.abs(r1-r2)+eps){
			double r=Math.min(r1, r2);
			return PI*r*r;
		}
		double x=(dis*dis+r1*r1-r2*r2)/(2*dis);
		double t1=Math.acos(x/r1);
		double t2=Math.acos((dis-x)/r2);
		return r1*r1*t1+r2*r2*t2-dis*r1*Math.sin(t1);
	}
	
    int cmp(double a,double b){  
        if(Math.abs(a-b)<eps)return 0;  
        else if(a<b) return -1;  
        else return 1;  
    }  
	
}