极为舒服的
计算几何终极模板+总结
小知识点
//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
return x;
}
const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;
//求正负符号
int sgn(double d) {
if(fabs(d)<eps) return 0;
if(d>0) return 1;
return -1;
}
//求x,y大小关系，y默认为0
int dcmp(double x, double y=0) {
if(fabs(x-y)<eps) return 0;
if(x>y) return 1;
return -1;
}
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) {
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool operator == (const Point &a, const Point &b) {
if(sgn(a.x-b.x)==0 && sgn(a.y-b.y)==0) return true;
return false;
}
//向量点乘，内积
double Dot(Vector A, Vector B) {
return A.x*B.x+A.y*B.y;
}
//向量叉乘，外积
double Cross(Vector A, Vector B) {
return A.x*B.y-A.y*B.x;
}
//向量长度
double Length(Vector A) {
return sqrt(Dot(A,A));
}
//二维向量夹角，rad值
double Angle(Vector A, Vector B) {
return acos(Dot(A,B)/Length(A)/Length(B));
}
//三角形面积的二倍
double Area2(Point A, Point B, Point C) {
return Cross(B-A,C-A);
}
//向量逆时针旋转rad角度
Vector Rotate(Vector A, double rad) {
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//向量A逆时针转90°后的单位向量
Vector Normal(Vector A) {
double L=Length(A);
return Vector(-A.y/L,A.x/L);
}
//判断bc是否在ab的逆时针方向，构造凸包时常用
bool ToLeftTest(Point a, Point b, Point c) {
return Cross(b-a,c-b)>0;
}
struct Line{
Point v, p;
Line(Point v, Point p):v(v), p(p) {}
Point point(double t) {
return v+(p-v)*t;
}
};
//求两直线交点，但需保证Cross(v,w)!=0，即两直线不能夹直角
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;
}
//点P到直线AB的距离公式
double DistanceToLine(Point P, Point A, Point B) {
Vector v1=B-A, v2=P-A;
return fabs(Cross(v1,v2)/Length(v1));
}
//点P到线段AB的距离公式
double DistanceToSegment(Point P, Point A, Point B) {
if(A==B) return Length(P-A);
Vector v1=B-A, v2=P-A, v3=P-B;
if(dcmp(Dot(v1,v2))<0) return Length(v2);
if(dcmp(Dot(v1,v3))>0) return Length(v3);
return DistanceToLine(P,A,B);
}
//点P在直线AB上的投影点
Point GetLineProjection(Point P, Point A, Point B) {
Vector v=B-A;
return A+v*(Dot(v,P-A)/Dot(v,v));
}
//判断点P是否在线段AB上,包含端点
bool OnSegment(Point p, Point a1, Point a2) {
return dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p))<=0;
}
//判断两条线段是否相交
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);
//若允许线段在端点处相交，则加入如下if判断,否则不需要
if(!sgn(c1)||!sgn(c2)||!sgn(c3)||!sgn(c4)) {
bool f1=OnSegment(b1,a1,a2);
bool f2=OnSegment(b2,a1,a2);
bool f3=OnSegment(a1,b1,b2);
bool f4=OnSegment(a2,b1,b2);
bool f=(f1|f2|f3|f4);
return f;
}
return sgn(c1)*sgn(c2)<0 && sgn(c3)*sgn(c4)<0;
}
//求多边形面积，p为顶点集合，n为顶点个数
//方法为从第一个顶点出发把凸多边形分成n-2个三角形(另外一个常用的方法就自己写吧)
//顶点应按照逆时针顺序排列！！！关键点
double PolygonArea(Point *p, int n) {
double s=0;
for(int i=1; i<n-1; ++i) s+=Cross(p[i]-p[0],p[i+1]-p[0]);
return s/2;
}
//判断点是否在多边形内(不保证凸多边形)
//若点在多边形内返回1，在多边形外部返回0，在多边形上返回-1
//若要判断在凸多边形内，则只需判断是否此点在所有边的左边
int isPointInPolygon(Point p, vector<Point> poly) {
int wn=0;
int n=poly.size();
for(int i=0; i<n; ++i) {
if(OnSegment(p,poly[i],poly[(i+1)%n])) return -1;
int k=sgn(Cross(poly[(i+1)%n]-poly[i],p-poly[i]));
int d1=sgn(poly[i].y-p.y);
int d2=sgn(poly[(i+1)%n].y-p.y);
if(k>0&&d1<=0&&d2>0) wn++;
if(k<0&&d2<=0&&d1>0) wn--;
}
if(wn!=0) return 1;
return 0;
}
struct Circle{
Point c;
double r;
Circle(Point c, double r):c(c), r(r) {}
Point point(double a) { //通过圆心角求坐标
return Point(c.x+cos(a)*r,c.y+sin(a)*r);
}
};
//求圆与直线的交点，交点存放在sol里面
int getLineCircleIntersection(Line L, Circle C, double &t1, double &t2, vector<Point> &sol) {
double a=L.v.x, b=L.p.x-C.c.x, c=L.v.y, d=L.p.y-C.c.y;
double e=a*a+c*c, f=2*(a*b+c*d), g=b*b+d*d-C.r*C.r;
double delta=f*f-4*e*g;
if(sgn(delta)<0) return 0; //相离
if(sgn(delta)==0) { //相切
t1=-f/(2*e);
t2=-f/(2*e);
sol.push_back(L.point(t1));
return 1;
}
//相交
t1=(-f-sqrt(delta))/(2*e);
sol.push_back(L.point(t1));
t2=(-f+sqrt(delta))/(2*e);
sol.push_back(L.point(t2));
return 2;
}
//两个圆相交的面积
double AreaOfOverlap(Point c1, double r1, Point c2, double r2) {
double d=Length(c1-c2);
if(r1+r2<d+eps) return 0.0;
if(d<fabs(r1-r2)+eps) {
double r=min(r1,r2);
return acos(-1)*r*r;
}
double x=(d*d+r1*r1-r2*r2)/(2.0*d);
double p=(r1+r2+d)/2.0;
double t1=acos(x/r1);
double t2=acos((d-x)/r2);
double s1=r1*r1*t1;
double s2=r2*r2*t2;
double s3=2*sqrt(p*(p-r1)*(p-r2)*(p-d));
return s1+s2-s3;
}
//求解凸包，GrahamScan算法，复杂度nlogn
//顶点编号从0到n-1
//凸包顶点(编号为排序后的编号)保存在stk数组中，从0到top-1
Point lst[maxn];
int stk[maxn], top;
bool cmp(Point p1, Point p2) {
int tmp=sgn(Cross(p1-lst[0],p2-lst[0]));
if(tmp>0) return true;
if(tmp==0&&Length(lst[0]-p1)<Length(lst[0]-p2)) return true;
return false;
}
void Graham(int n) {
int k=0;
Point p0;
p0.x=lst[0].x;
p0.y=lst[0].y;
for(int i=1; i<n; ++i) {
if(p0.y>lst[i].y || (p0.y==lst[i].y&&p0.x>lst[i].x)) {
p0.x=lst[i].x;
p0.y=lst[i].y;
k=i;
}
}
lst[k]=lst[0];
lst[0]=p0;
sort(lst+1,lst+n,cmp);
if(n==1) { top=1; stk[0]=0; return; }
if(n==2) { top=2; stk[0]=0; stk[1]=1; return; }
stk[0]=0, stk[1]=1, top=2;
for(int i=2; i<n; ++i) {
while(top>1&&Cross(lst[stk[top-1]]-lst[stk[top-2]],lst[i]-lst[stk[top-2]])<=0) --top;
stk[top]=i, ++top;
}
}
int main() {
//ios::sync_with_stdio(false);
}
京公网安备 11010502036488号