好友
阅读权限10
听众
最后登录1970-1-1
|
首先声明,本人是一名渣ACMer,为了代码写作的速度,代码风格和实现方式以 单文件,函数式 为主,使用C++的头文件和函数库(包括STL),对此不喜的吐槽可以,勿喷!!!
另,本人在CSDN的blog同步更新,ID也是sinianluoye 不要说我是非原创哦0.0
欢迎测试,欢迎纠错,欢迎改进方案,欢迎交流,欢迎各种吐槽~
新人发帖,有什么做的不对的地方,你们还是告诉我吧- -!
先贴函数的列表~
所在行 | 函数(结构)声明 | 功能 | 23 | int sign(double d) | 返回浮点数的符号 | 24 | bool isint(double d) | 判断一个浮点数是不是整数 | 25 | bool Equal(double a,double b) | 判断两个浮点数是否相等 | 28 | struct Point | 点定义 | 13 | NAP | 不是一个点 | 34 | bool isnap(const Point& P) | 判断一个点是不是NAP | 40 | typedef Point Vector; | 向量定义 | 42 | Vector operator + (Vector A,Vector B) | 向量相加 | 43 | Vector operator - (Vector A,Vector B) | 向量相减 | 44 | Vector operator * (Vector A,double t) | 数乘向量 | 45 | Vector operator * (double t,Vector A) | 数乘向量 | 46 | Vector operator / (Vector A,double t) | 向量除数 | 49 | bool operator < (const Point& a,const Point& b) | 坐标从左到右从下到上的比较 | 50 | bool operator == (const Point& a,const Point& b) | 坐标从左到右从下到上的比较 | 51 | bool operator > (const Point& a,const Point& b) | 坐标从左到右从下到上的比较 | 52 | bool operator <= (const Point& a,const Point& b) | 坐标从左到右从下到上的比较 | 53 | bool operator >= (const Point& a,const Point& b) | 坐标从左到右从下到上的比较 | 55 | double Dot(const Point& A,const Point& B) | 点积 | 56 | double Cross(const Point& A,const Point& B) | 叉积 | 57 | double Length(const Point& A) | 模 | 58 | double Length(const Point& A,const Point& B) | 两点间距 | 59 | double Distance(const Point& A,const Point& B) | 两点间距 | 60 | double Angle(const Point& A,const Point& B) | 两向量夹角 | 61 | double Area2(const Point& A,const Point& B,const Point& C) | 三角形有向面积 | 63 | Vector Rotate(const Vector& A,double rad) | 向量绕起点旋转rad弧度 | 64 | Vector Normal(const Vector& A) | 单位法向量 | 65 | Vector Unit(const Vector& A) | 单位向量 | 67 | bool Collinear(const Point& A,const Point& B,const Point& C) | 判断三点是否共线 | 72 | struct Segment | 线段定义 | 77 | struct Line | 直线定义 | 14 | NAS | 不是一个线段(直线) | 84 | bool isnas(const Segment& S) | 判断是否为NAS | 91 | bool Online(const Point& P,const Line& L) | 点在直线上 | 92 | bool Online(const Point& P,const Segment& L) | 点在线段上 不包括端点 | 93 | bool Online_ex(const Point& P,const Segment& L) | 点在线段上 包括端点 | 95 | int Side(const Point& P,Line L) | 点对于直线的位置 | 96 | int Side(const Point& P,Segment L) | 点对于直线的位置 | 97 | bool SameSide(const Point& P1,const Point& P2,const Line& L) | 两点在直线同侧判定 不包含在直线上 | 98 | bool SameSide(const Point& P1,const Point& P2,const Segment& L) | 两点在线段同侧判定 不包含在线段所在直线上 | 99 | bool SameSide_ex(const Point& P1,const Point& P2,const Line& L) | 两点在直线同侧判定 包含在直线上 | 100 | bool SameSide_ex(const Point& P1,const Point& P2,const Segment& L) | 两点在线段同侧判定 包含在线段所在直线上 | 103 | bool Parallel(const Line& L1,const Line& L2) | 平行或重合判定 | 104 | Equal(const Line& L1,const Line& L2) | 重合判定 | 105 | bool operator == (const Line& L1,const Line& L2) | 重合判定 | 106 | bool Vertical(const Line& L1,const Line& L2) | 垂直判定 | 109 | bool Parallel(const Segment& L1,const Segment& L2) | 线段平行或共线 | 110 | bool Collinear(const Segment& L1,const Segment& L2) | 判定共线 | 111 | bool Equal(const Segment& L1,const Segment& L2) | 线段相等判定 | 112 | bool operator == (const Segment& L1,const Segment& L2) | 线段相等判定 | 113 | bool Intersec(const Segment& L1,const Segment& L2) | 判断两线段是否相交 不包括端点 | 114 | bool Intersec_ex(const Segment& L1,const Segment& L2) | 判断两线段是否相交 包括端点 | 122 | double Distance(const Line& L,const Point& P) | 点到直线距离 | 123 | double Distance(const Segment& S,const Point& P) | 点到线段距离 | 131 | double Length(const Segment& S) | 线段长度 | 133 | Point Intersection(const Line& L1,const Line& L2) | 两直线交点 | 140 | Point Intersection(const Segment& L1,const Segment& L2) | 两线段交点 不包含端点 | 146 | Point Intersection_ex(const Segment& L1,const Segment& L2) | 两线段交点 包含端点 | 153 | Point LineSymmetry(const Line&symmetryline,const Point& P) | 点关于直线的对称点 | 160 | Point LineSymmetry(const Segment&symmetryline,const Point& P) | 点关于线段的对称点 | 167 | Line LineSymmetry(const Line&symmetryline,const Line& L) | 直线关于直线的对称线 | 170 | Segment LineSymmetry(const Line&symmetryline,const Segment& L) | 线段关于直线的对称线 | 173 | Line LineSymmetry(const Segment&symmetryline,const Line& L) | 直线关于线段的对称线 | 176 | Segment LineSymmetry(const Segment&symmetryline,const Segment& L) | 线段关于线段的对称线 | 179 | Point PointSymmetry(const Point&symmetrypoint,const Point& P) | 中心对称 | 181 | Segment PointSymmetry(const Point&Symmetrypoint,const Segment& L) | 线段关于点的中心对称 | 184 | Line PointSymmetry(const Point&Symmetrypoint,const Line& L) | 直线关于点的中心对称 | 189 | Point Projection(const Line& L,const Point& P) | 点在直线上的投影 | 196 | Point Projection(const Segment& L,const Point& P) | 点对线段的投影 | 203 | Segment Projection(const Line& L,const Segment& S) | 线段在直线上的投影 | 210 | Point Midpoint(const Segment& S) | 中点 | 212 | Line Perpendicular(const Line& S,const Point& P) | 过定点的垂线 | 213 | Line PerpendicularBisector(const Segment& S) | 垂直平分线 | 215 | Line NormalLine(const Line& S,const Point& P) | 过定点垂线 | 216 | Line Midnormal(const Segment& S) | 垂直平分线 | 218 | Line AngleBisector(const Line& L1,const Line& L2) | 角平分线 | 232 | double Area(const Point& A,const Point& B,const Point& C) | 三角形面积 | 234 | Point Circumcenter(const Point& A,const Point& B,const Point& C) | 三角形外心 | 237 | Point Incenter(const Point& A,const Point& B,const Point& C) | 三角形内心 | 241 | Point Perpencenter(const Point& A,const Point& B,const Point& C) | 三角形垂心 | 244 | Point Barycentry(const Point& A,const Point& B,const Point& C) | 三角形重心 | 247 | struct Triangle | 三角形定义 | 254 | double Area(const Triangle& T) | 三角形面积 | 255 | Point Circumcenter(const Triangle& T) | 三角形外心 | 256 | Point Incenter(const Triangle& T) | 三角形内心 | 257 | Point Perpencenter(const Triangle& T) | 三角形垂心 | 258 | Point Barycentry(const Triangle& T) | 三角形重心 | 260 | int Type(const Triangle& T) | 返回三角形的类型 | 263 | bool InTriangle_ex(const Point& P,const Triangle& T) | 返回点是否在三角形内部(含边) | 266 | bool InTriangleLine(const Point& P,const Triangle& T) | 返回点是否在三角形边上(含端点) | 269 | bool InTriangle(const Point& P,const Triangle& T) | 返回点是否在三角形内部(不含边) | 276 | struct Polygon | 多边形定义 | 312 | double Area(const Polygon& P) | 多边形的面积 | 322 | Polygon ConvexHull_ex(Polygon P) | 凸包扫描算法(含平角) | 343 | int ConvexHull_ex(int n,Point *P,Point *ans) | 凸包扫描算法(含平角) | 351 | Polygon ConvexHull(Polygon P) | 凸包扫描算法(不含平角) | 372 | int ConvexHull(int n,Point *P,Point *ans) | 凸包扫描算法(不含平角) | 380 | bool IsConvex(const Polygon& P) | 判断是否为凸多边形 (凸多边形定义包含平角) | 389 | bool IsConvex(int n,Point *P) | 判断是否为凸多边形 | 394 | int InPolygon(const Point& P,const Polygon& POLY) | 点是否在多边形内部 | 412 | struct Circle | 圆的定义 | 419 | double Area(const Circle& C) | 圆的面积 | 421 | int Position(const Point& P,const Circle& C) | 返回点与圆的位置关系 | 426 | int Position(const Line& L,const Circle& C) | 返回直线与圆的位置关系 | 431 | Segment Intersection(const Line& L,const Circle& C) | 返回直线与圆的割线 | 453 | int Position(const Circle& C1,const Circle& C2) | 圆与圆的位置关系 | 471 | Segment Intersection(const Circle& C1,const Circle& C2) | 圆与圆的公共弦 |
下面是代码~ 更具体的请看相应函数的注释
[C++] 纯文本查看 复制代码 /*************************************二维几何模板***************************************************/
/*************************** lc思念落叶(sinianluoye、JLU_Lichuang) 2015-3-10***********************/
#include <cmath>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#define eps 1e-8
#define sqr(x) ((x)*(x))
#define NAP Point(NAN,NAN)
#define NAS Segment(NAP,NAP)
using namespace std;
/***1.点与向量的基本定义***/
const double pi=acos(-1);
int sign(double d){if(fabs(d)<eps)return 0;return (d<0)?-1:1;} ///返回浮点数的符号
bool isint(double d){return fabs(floor(d+0.5)-d)<eps;} ///判断一个浮点数是不是整数
bool Equal(double a,double b){return fabs(a-b)<eps;}///判断两个浮点数是否相等
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
bool isnap(const Point& P)
{
return isnan(P.x)||isnan(P.y);
}
typedef Point Vector;
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}///向量相加
Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}///向量相减
Vector operator * (Vector A,double t){return Vector(A.x*t,A.y*t);}///数乘向量
Vector operator * (double t,Vector A){return Vector(A.x*t,A.y*t);}///数乘向量
Vector operator / (Vector A,double t){return Vector(A.x/t,A.y/t);}///向量除数
/**以下比较基于点的坐标从左到右从下到上**/
bool operator < (const Point& a,const Point& b){if(sign(a.x-b.x))return a.x<b.x;return a.y<b.y;}
bool operator == (const Point& a,const Point& b){return !(sign(a.x-b.x)||sign(a.y-b.y));}
bool operator > (const Point& a,const Point& b){return !((a<b)||(a==b));}
bool operator <= (const Point& a,const Point& b){return !(a>b);}
bool operator >= (const Point& a,const Point& b){return !(a<b);}
double Dot(const Point& A,const Point& B){return A.x*B.x+A.y*B.y;}///点积
double Cross(const Point& A,const Point& B){return A.x*B.y-A.y*B.x;}///叉积
double Length(const Point& A){return sqrt(Dot(A,A));}///模
double Length(const Point& A,const Point& B){return Length(A-B);}///两点间距
double Distance(const Point& A,const Point& B){return Length(A-B);}///两点间距
double Angle(const Point& A,const Point& B){return acos(Dot(A,B)/Length(A)/Length(B));}///两向量夹角
double Area2(const Point& A,const Point& B,const Point& C){return 0.5*Cross(B-A,C-A);}///三角形的有向面积
Vector Rotate(const Vector& A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}///向量绕起点旋转rad弧度
Vector Normal(const Vector& A){double L=Length(A);return Vector(-A.y/L,A.x/L);}///单位法向量
Vector Unit(const Vector& A){double L=Length(A);return Vector(A.x/L,A.y/L);}///单位向量
bool Collinear(const Point& A,const Point& B,const Point& C){return !sign(Cross(A-B,A-C));}///判断三点是否共线
/***2.直线射线线段相关***/
///a,b为线段的两端点(直线上的两点) v为方向向量
struct Segment
{
Point a,b,v;
Segment(Point a=Point(),Point b=Point()):a(a),b(b),v(b-a){}
};///线段
struct Line
{
Point a,b,v;
Line(Point a=Point(),Point b=Point()):a(a),b(b),v(b-a){}
Line(Segment S):a(S.a),b(S.b),v(S.v){}
};///直线
bool isnas(const Segment& S)
{
return isnap(S.a)||isnap(S.b);
}
///点与直线线段的位置关系
bool Online(const Point& P,const Line& L){return !sign(Cross(P-L.a,L.v));}///点在直线上
bool Online(const Point& P,const Segment& L){return (Online(P,Line(L))&&(sign(Dot(P-L.a,L.v))>0)&&(sign(Dot(L.b-P,L.v))>0));}///点在线段上 不包括端点
bool Online_ex(const Point& P,const Segment& L){return (Online(P,Line(L))&&(sign(Dot(P-L.a,L.v))>=0)&&(sign(Dot(L.b-P,L.v))>=0));}///点在线段上 包括端点
int Side(const Point& P,Line L){if(L.a>L.b)swap(L.a,L.b);return sign(Area2(L.a,L.b,P));}///返回点对于直线的位置 1(左(上)边) 0(在直线上) -1在(右(下)边)
int Side(const Point& P,Segment L){if(L.a>L.b)swap(L.a,L.b);return sign(Area2(L.a,L.b,P));}///返回点对于直线的位置 1(左(上)边) 0(在线段所在直线上) -1在(右(下)边)
bool SameSide(const Point& P1,const Point& P2,const Line& L){return Side(P1,L)*Side(P2,L)==1;}///两点在直线同侧判定 不包含在直线上
bool SameSide(const Point& P1,const Point& P2,const Segment& L){return Side(P1,L)*Side(P2,L)==1;}///两点在线段同侧判定 不包含在线段所在直线上
bool SameSide_ex(const Point& P1,const Point& P2,const Line& L){return Side(P1,L)*Side(P2,L)>=0;}///两点在直线同侧判定 包含在直线上
bool SameSide_ex(const Point& P1,const Point& P2,const Segment& L){return Side(P1,L)*Side(P2,L)>=0;}///两点在线段同侧判定 包含在线段所在直线上
///直线位置关系
bool Parallel(const Line& L1,const Line& L2){return !sign(Cross(L1.v,L2.v));}///平行和重合都返回1 注意重合!!!
bool Equal(const Line& L1,const Line& L2){Line T(L1.a,L2.a);return Parallel(L1,L2)&&Parallel(L1,T);}///重合判定
bool operator == (const Line& L1,const Line& L2){return Equal(L1,L2);}
bool Vertical(const Line& L1,const Line& L2){return !sign(Dot(L1.v,L2.v));}///垂直判定
///线段位置关系
bool Parallel(const Segment& L1,const Segment& L2){return !sign(Cross(L1.v,L2.v));}///线段平行或共线都返回1 注意共线!!!
bool Collinear(const Segment& L1,const Segment& L2){return Parallel(L1,L2)&&Collinear(L1.a,L1.b,L2.a);}///判定共线
bool Equal(const Segment& L1,const Segment& L2){return L1.a==L2.a&&L1.b==L2.b;}///线段相等判定
bool operator == (const Segment& L1,const Segment& L2){return Equal(L1,L2);}
bool Intersec(const Segment& L1,const Segment& L2){return ((Side(L1.a,L2)*Side(L1.b,L2))<0)&&(Side(L2.a,L1)*Side(L2.b,L1)<0);}///判断两线段是否相交不包括端点
bool Intersec_ex(const Segment& L1,const Segment& L2)
{
int s1=Side(L1.a,L2),s2=Side(L1.b,L2),s3=Side(L2.a,L1),s4=Side(L2.b,L1);
return (s1||s2)&&(s3||s4);
}///判断两线段是否相交包括端点
///交点、对称点、距离
double Distance(const Line& L,const Point& P){return fabs(Cross(P-L.a,L.v)/Length(L.v));}///点到直线距离
double Distance(const Segment& S,const Point& P)///点到线段距离
{
if(sign(Dot(P-S.a,S.v))<=0)
return Distance(P,S.a);
if(sign(Dot(P-S.b,S.v))<=0)
return Distance(P,S.b);
return fabs(Cross(P-S.a,S.v)/Length(S.v));
}
double Length(const Segment& S){return Length(S.a,S.b);}///线段长度
Point Intersection(const Line& L1,const Line& L2)///两直线交点 请先判断是否平行
{
Vector u=L1.a-L2.a;
double t=Cross(L2.v,u)/Cross(L1.v,L2.v);
return L1.a+L1.v*t;
}
Point Intersection(const Segment& L1,const Segment& L2)///两线段交点 不包含端点 不相交的线段返回(NAN,NAN)
{
if(Intersec(L1,L2))
return Intersection(Line(L1),Line(L2));
return NAP;
}
Point Intersection_ex(const Segment& L1,const Segment& L2)///两线段交点 包含端点 不相交的线段返回(NAN,NAN)
{
if(Intersec_ex(L1,L2))
return Intersection(Line(L1),Line(L2));
return NAP;
}
Point LineSymmetry(const Line&symmetryline,const Point& P)///点关于直线的对称点
{
Vector u=P-symmetryline.a,v=Normal(symmetryline.v),w=symmetryline.v;
double t=Cross(w,u)/Cross(v,w);
return P+2*t*v;
}
Point LineSymmetry(const Segment&symmetryline,const Point& P)///点关于线段的对称点
{
Vector u=P-symmetryline.a,v=Normal(symmetryline.v),w=symmetryline.v;
double t=Cross(w,u)/Cross(v,w);
return P+2*t*v;
}
Line LineSymmetry(const Line&symmetryline,const Line& L)///直线关于直线的对称线
{return Line(LineSymmetry(symmetryline,L.a),LineSymmetry(symmetryline,L.b));}
Segment LineSymmetry(const Line&symmetryline,const Segment& L)///线段关于直线的对称线
{return Segment(LineSymmetry(symmetryline,L.a),LineSymmetry(symmetryline,L.b));}
Line LineSymmetry(const Segment&symmetryline,const Line& L)///直线关于线段的对称线
{return Line(LineSymmetry(symmetryline,L.a),LineSymmetry(symmetryline,L.b));}
Segment LineSymmetry(const Segment&symmetryline,const Segment& L)///线段关于线段的对称线
{return Segment(LineSymmetry(symmetryline,L.a),LineSymmetry(symmetryline,L.b));}
Point PointSymmetry(const Point&symmetrypoint,const Point& P){return 2*symmetrypoint-P;}///中心对称
Segment PointSymmetry(const Point&Symmetrypoint,const Segment& L)///线段关于点的中心对称
{return Segment(PointSymmetry(Symmetrypoint,L.a),PointSymmetry(Symmetrypoint,L.b));}
Line PointSymmetry(const Point&Symmetrypoint,const Line& L)///直线关于点的中心对称
{return Segment(PointSymmetry(Symmetrypoint,L.a),PointSymmetry(Symmetrypoint,L.b));}
Point Projection(const Line& L,const Point& P)///点在直线上的投影
{
Vector u=P-L.a,v=Normal(L.v),w=L.v;
double t=Cross(w,u)/Cross(v,w);
return P+t*v;
}
Point Projection(const Segment& L,const Point& P)///点对线段的投影(不一定在线段上)
{
Vector u=P-L.a,v=Normal(L.v),w=L.v;
double t=Cross(w,u)/Cross(v,w);
return P+t*v;
}
Segment Projection(const Line& L,const Segment& S)///线段在直线上的投影
{
return Segment(Projection(L,S.a),Projection(L,S.b));
}
///线段相关
Point Midpoint(const Segment& S){return 0.5*(S.a+S.b);}///中点
Line Perpendicular(const Line& S,const Point& P){return Line(P,P+Normal(S.v));}///过定点的垂线
Line PerpendicularBisector(const Segment& S){return Perpendicular(S,Midpoint(S));}///垂直平分线
Line NormalLine(const Line& S,const Point& P){return Line(P,P+Normal(S.v));}///过定点垂线(上边的名太长了 这个好记些 下同)
Line Midnormal(const Segment& S){return Perpendicular(S,Midpoint(S));}///垂直平分线
Line AngleBisector(const Line& L1,const Line& L2)///角平分线
///注意这里L1 L2为射线 方向分别为 L1.v即(L1.b-L1.a),L2.v即(L2.b-L2.a) 函数输入只需保证方向正确且L1,L2不平行即可
{
Point P=Intersection(L1,L2);
Vector V=Unit(L1.v)+Unit(L2.v);
if(Length(V)>eps)
return Line(P,P+V);
return NormalLine(L1,L1.a);
}
/********************************二维图形相关**********************************************/
///三角形
double Area(const Point& A,const Point& B,const Point& C){return fabs(Area2(A,B,C));}///三角形面积
Point Circumcenter(const Point& A,const Point& B,const Point& C)
{return Intersection(Midnormal(Segment(A,B)),Midnormal(Segment(A,C)));}///三角形外心
Point Incenter(const Point& A,const Point& B,const Point& C)
{return Intersection(AngleBisector(Line(A,B),Line(A,C)),AngleBisector(Line(B,C),Line(B,A)));}///三角形内心
Point Perpencenter(const Point& A,const Point& B,const Point& C)
{return Intersection(Perpendicular(Line(A,B),C),Perpendicular(Line(A,C),B));}/// 三角形垂心
Point Barycentry(const Point& A,const Point& B,const Point& C)
{return (A+B+C)/3.0;}///三角形重心
struct Triangle
{
Point A,B,C;
Triangle(Point A=Point(),Point B=Point(),Point C=Point())
:A(A),B(B),C(C){}
};
double Area(const Triangle& T){return Area(T.A,T.B,T.C);}///面积
Point Circumcenter(const Triangle& T){return Circumcenter(T.A,T.B,T.C);}///外心
Point Incenter(const Triangle& T){return Incenter(T.A,T.B,T.C);}///内心
Point Perpencenter(const Triangle& T){return Perpencenter(T.A,T.B,T.C);}///垂心
Point Barycentry(const Triangle& T){return Barycentry(T.A,T.B,T.C);}///重心
int Type(const Triangle& T)///返回三角形的类型 -1 钝角 0直角 1 锐角
{return sign(Dot(T.A-T.B,T.A-T.C)*Dot(T.B-T.A,T.B-T.C)*Dot(T.C-T.A,T.C-T.B));}
bool InTriangle_ex(const Point& P,const Triangle& T)///返回点是否在三角形内部(含边)
{return !sign(Area(P,T.A,T.B)+Area(P,T.A,T.C)+Area(P,T.B,T.C)-Area(T));}
bool InTriangleLine(const Point& P,const Triangle& T)///返回点是否在三角形边上(含端点)
{return Online_ex(P,Segment(T.A,T.B))||Online_ex(P,Segment(T.A,T.C))||Online_ex(P,Segment(T.C,T.B));}
bool InTriangle(const Point& P,const Triangle& T)///返回点是否在三角形内部(不含边)
{return InTriangle_ex(P,T)&&!InTriangleLine(P,T);}
///多边形
struct Polygon
{
int n;
Point *P;
Polygon(int nums=0,Point *point=NULL)
{
if(nums>2)
{
P=new Point[n=nums];
for(int i=0;i<n;i++)
P[i]=point[i];
}
else
{
n=0,P=NULL;
}
}
Polygon(const Polygon& T)
{
n=T.n;
P=new Point[n];
for(int i=0;i<n;i++)
P[i]=T[i];
}
Point& operator [](int key)
{
return P[key];
}
const Point& operator [](int key)const
{
return P[key];
}
};
double Area(const Polygon& P)///多边形的面积
{
double ret=0;
for(int i=1;i<P.n-1;i++)
{
ret+=Area2(P[0],P[i],P[i+1]);
}
return fabs(ret);
}
Polygon ConvexHull_ex(Polygon P)///凸包扫描算法(含平角)
{
sort(P.P,P.P+P.n);
Polygon ret(P.n,P.P);
int n=P.n,&m=P.n;
m=0;
for(int i=0;i<n;i++)
{
while(m>1&&sign(Cross(ret[m-1]-ret[m-2],P[i]-ret[m-2]))<0)m--;
ret[m++]=P[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&sign(Cross(ret[m-1]-ret[m-2],P[i]-ret[m-2]))<0)m--;
ret[m++]=P[i];
}
if(m>1)m--;
return ret;
}
int ConvexHull_ex(int n,Point *P,Point *ans)///凸包扫描算法(含平角)
{
Polygon ret=ConvexHull_ex(Polygon(n,P));
for(int i=0;i<ret.n;i++)
ans[i]=ret[i];
return ret.n;
}
Polygon ConvexHull(Polygon P)///凸包扫描算法(不含平角)
{
sort(P.P,P.P+P.n);
Polygon ret(P.n,P.P);
int n=P.n,&m=P.n;
m=0;
for(int i=0;i<n;i++)
{
while(m>1&&sign(Cross(ret[m-1]-ret[m-2],P[i]-ret[m-2]))<=0)m--;
ret[m++]=P[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&sign(Cross(ret[m-1]-ret[m-2],P[i]-ret[m-2]))<=0)m--;
ret[m++]=P[i];
}
if(m>1)m--;
return ret;
}
int ConvexHull(int n,Point *P,Point *ans)///凸包扫描算法(不含平角)
{
Polygon ret=ConvexHull(Polygon(n,P));
for(int i=0;i<ret.n;i++)
ans[i]=ret[i];
return ret.n;
}
bool IsConvex(const Polygon& P)///判断是否为凸多边形 (凸多边形定义包含平角)
{
if(P.n<=3)return 1;
int t=sign(Area2(P[0],P[1],P[2]));
for(int i=1;i<P.n-2;i++)
if(t*sign(Area2(P[i],P[i+1],P[i+2]))<0)return 0;
return 1;
}
bool IsConvex(int n,Point *P)///判断是否为凸多边形
{
return IsConvex(Polygon(n,P));
}
int InPolygon(const Point& P,const Polygon& POLY)///返回点是(1)否(0)在多边形内部 负数为在PLOY[-i]和[(-i+1)%n]的线段上
{
int ret=0,n=POLY.n;
for(int i=0;i<n;i++)
{
if(Online_ex(P,Segment(POLY[i],POLY[(i+1)%n])))
return -i;
int t=sign(Cross(POLY[(i+1)%n]-POLY[i],P-POLY[i]));
int d1=sign(POLY[i].y-P.y);
int d2=sign(POLY[(i+1)%n].y-P.y);
if(t>0&&d1<=0&&d2>0)ret++;
if(t<0&&d2<=0&&d1>0)ret--;
}
return ret!=0;
}
///圆
struct Circle
{
Point C;
double r;
Circle(Point C=Point(),double r=0.0):C(C),r(r){}
};
double Area(const Circle& C){return pi*sqr(C.r);}
int Position(const Point& P,const Circle& C)///返回点与圆的位置关系 -1 内部 0 圆上 1 外部
{
return sign(Length(P,C.C)-C.r);
}
int Position(const Line& L,const Circle& C)///返回直线与圆的位置关系 -1 相离 0 相切 1 相交
{
return -sign(Distance(L,C.C)-C.r);
}
Segment Intersection(const Line& L,const Circle& C)
///返回直线与圆的交点 相交时返回割线(两端点即为交点) 相切时返回切点(返回线段的两个端点都相同)
///相离时返回 NAS
{
double d=sqr(C.r)-sqr(Distance(L,C.C));
if(sign(d)>0)
{
d/=Dot(L.v,L.v);
d=sqrt(d);
double dx=L.v.x*d,dy=L.v.y*d;
Point t=Projection(L,C.C),D(dx,dy);
return Segment(t+D,t-D);
}
else if(sign(d)==0)
{
Point ret=Projection(L,C.C);
return Segment(ret,ret);
}
else
return NAS;
}
int Position(const Circle& C1,const Circle& C2)
/// 圆与圆的位置关系
///0 相交 1 外切 -1内切 2 相离 -2 内含
{
double d=Distance(C1.C,C2.C);
switch(sign(d-C1.r-C2.r))
{
case -1:return 2;
case 0:return 1;
}
switch(sign(fabs(C1.r-C2.r)-d))
{
case 0:return -1;
case 1:return -2;
}
return 0;
}
Segment Intersection(const Circle& C1,const Circle& C2)
/// 圆与圆的公共弦 不相交返回 NAS
{
int key=Position(C1,C2);
if(!key)
{
double d=Distance(C1.C,C2.C);
double s=C1.r+C2.r+d;
s/=2;
double h2=4.0*s*(s-C1.r)*(s-C2.r)*(s-d)/d/d;
double l=sqrt(sqr(C1.r)-h2);
Point D=(C2.C-C1.C)*(l/d)+C1.C;
double h=sqrt(h2);
Line L=NormalLine(Line(C1.C,C2.C),D);
return Intersection(L,C1);
}
else if(abs(key)==1)
{
Point ret=C1.r/(Distance(C1.C,C2.C))*(C2.C-C1.C)+C1.C;
return Segment(ret,ret);
}
else return NAS;
}
/*************copyright by sinianluoye (JLU_LiChuang)***********/
再次欢迎测试,欢迎纠错,欢迎改进方案,欢迎交流,欢迎各种吐槽~
and~ 有什么想要的功能这里没实现的也请告诉我,我会尽力去实现的
cpp和函数列表也添加到了附件里的哦~
|
-
-
二维几何模板.rar
15.05 KB, 下载次数: 20, 下载积分: 吾爱币 -1 CB
一个cpp一个excel
|