首页 > 代码库 > weeping专用模板--更新中
weeping专用模板--更新中
自己的模板
/* 二维几何 */
/* 需要包含的头文件 */
#include<cstdio>
#include <cstring>
#include <cmath >
#include <iostream>
#include <algorithm>
using namespace std;
/** 常用的常量定义 **/
const double INF = 1e200;
const double eps = 1e-10;
const double PI = acos(-1.0);
const int Max = 1e6;
/** 基本几何结构 **/
struct Point
{
double x,y;
Point(double a=0, double b=0){x=a,y=b;}
bool operator<(const Point &ta)const
{
if(x==ta.x) return y<ta.y;
return x<ta.x;
}
friend Point operator+(const Point &ta,const Point &tb)
{
return Point(ta.x+tb.x,ta.y+tb.y);
}
friend Point operator-(const Point &ta,const Point &tb)
{
return Point(ta.x-tb.x,ta.y-tb.y);
}
};
struct Vec2D ///二维向量,*重载为点乘,/重载为叉乘
{
double x,y;
Vec2D(double ta,double tb){x=ta,y=tb;}
Vec2D(Point &ta){x=ta.x,y=ta.y;}
friend double operator*(const Vec2D &ta,const Vec2D &tb)
{
return ta.x*tb.x+ta.y*tb.y;
}
friend double operator/(const Vec2D &ta,const Vec2D &tb)
{
return ta.x*tb.y-ta.y*tb.x;
}
friend Vec2D operator+(const Vec2D &ta,const Vec2D &tb)
{
return Vec2D(ta.x+tb.x,ta.y+tb.y);
}
friend Vec2D operator-(const Vec2D &ta,const Vec2D &tb)
{
return Vec2D(ta.x-tb.x,ta.y-tb.y);
}
Vec2D operator=(const Vec2D &ta)
{
x=ta.x,y=ta.y;
return *this;
}
};
struct LineSeg ///线段,重载了/作为叉乘运算符,*作为点乘运算符
{
Point s,e;
LineSeg(){s=Point(0,0),e=Point(0,0);}
LineSeg(Point a, Point b){s=a,e=b;}
double lenth(void)
{
return sqrt((s.x-e.x)*(s.x-e.x)+(s.y-e.y)*(s.y-e.y));
}
friend double operator*(const LineSeg &ta,const LineSeg &tb)
{
return (ta.e.x-ta.s.x)*(tb.e.x-tb.s.x)+(ta.e.y-ta.s.y)*(tb.e.y-tb.s.y);
}
friend double operator/(const LineSeg &ta,const LineSeg &tb)
{
return (ta.e.x-ta.s.x)*(tb.e.y-tb.s.y)-(ta.e.y-ta.s.y)*(tb.e.x-tb.s.x);
}
LineSeg operator=(const LineSeg &ta)
{
s=ta.s,e=ta.e;
return *this;
}
};
struct Line /// 直线的解析方程 a*x+b*y+c=0 为统一表示,约定 a >= 0
{
double a,b,c;
Line(double d1=1, double d2=-1, double d3=0){ a=d1,b=d2,c=d3;}
};
int sgn(double ta,double tb);
double fArea(Point &ta,Point &tb,Point &tc);
bool intersect(LineSeg &lx,LineSeg &ly);
bool intersection(LineSeg &lx,LineSeg &ly,Point &pt);
double getdis(const Point &ta,const Point &tb);
bool cmp(const Point &ta,const Point &tb);
void graham(Point ps[],Point tb[],int n,int &num);
void ConvexClosure(Point ps[],Point tb[],int n,int &num);
int main(void)
{
return 0;
}
/*******判断ta与tb的大小关系*******/
int sgn(double ta,double tb)
{
if(fabs(ta-tb)<eps)return 0;
if(ta<tb) return -1;
return 1;
}
/*********求两点的距离*************/
double getdis(const Point &ta,const Point &tb)
{
return sqrt((ta.x-tb.x)*(ta.x-tb.x)+(ta.y-tb.y)*(ta.y-tb.y));
}
/************三角形面积**************************/
double fArea(Point &ta,Point &tb,Point &tc)
{
return fabs(LineSeg(ta,tb)/LineSeg(ta,tc)*0.5);
}
/*********** 判断P1P2是否和P3P4相交****************************
其中Pi坐标为(xi,yi),需要满足两个条件:
(1)快速排斥试验:
以P1P2为对角线的矩形S1是否和以P3P4为对角线的矩形S2相交,
即 min(x1,x2)<=max(x3,x4) && min(x3,x4)<=max(x1,x2)
&& min(y1,y2)<=max(y3,y4) &&min(y3,y4)<=max(y1,y2)
(2)跨立试验:
点P1,P2必然在线段P3P4的不同侧,
点P3,P4必然在线段P1P2的不同侧,
***************************************************************/
bool intersect(LineSeg &lx,LineSeg &ly)
{
return sgn(min(lx.s.x,lx.e.x),max(ly.s.x,ly.e.x))<=0
&& sgn(min(ly.s.x,ly.e.x),max(lx.s.x,lx.e.x))<=0
&& sgn(min(lx.s.y,lx.e.y),max(ly.s.y,ly.e.y))<=0
&& sgn(min(ly.s.y,ly.e.y),max(lx.s.y,lx.e.y))<=0
&& sgn((lx/LineSeg(lx.s,ly.s))*(lx/LineSeg(lx.s,ly.e)),0)<=0
&& sgn((ly/LineSeg(ly.s,lx.s))*(ly/LineSeg(ly.s,lx.e)),0)<=0;
}
/************线段求交点**************************
返回-1代表直线平行,返回0代表直线重合,返回1代表线段相交
利用叉积求得点P分线段DC的比,
然后利用高中学习的定比分点坐标公式求得分点P的坐标
**************************************************/
bool intersection(LineSeg &lx,LineSeg &ly,Point &pt)
{
pt=lx.s;
if(sgn(lx/ly,0)==0)
{
if(sgn(LineSeg(lx.s,ly.e)/ly,0)==0)
return 0;//重合
return -1;//平行
}
double t = (LineSeg(lx.s,ly.s)/ly)/(lx/ly);
pt.x+=(lx.e.x-lx.s.x)*t, pt.y+=(lx.e.y-lx.s.y)*t;
return 1;
}
/** ************凸包算法****************
寻找凸包的graham 扫描法
PS(PointSet)为输入的点集;
tb为输出的凸包上的点集,按照逆时针方向排列;
n为PointSet中的点的数目
num为输出的凸包上的点的个数
****************************************** **/
bool cmp(const Point &ta,const Point &tb)/// 选取与最后一条确定边夹角最小的点,即余弦值最大者
{
// double tmp=LineSeg(ps[0],ta)/LineSeg(ps[0],tb);
// if(sgn(tmp,0)==0)
// return getdis(ps[0],ta)<getdis(ps[0],tb);
// else if(tmp>0)
// return 1;
return 0;
}
void graham(Point ps[],Point tb[],int n,int &num)
{
int cur=0,top=2;
for(int i=1;i<n;i++)
if(sgn(ps[cur].y,ps[i].y)>0 || (sgn(ps[cur].y,ps[i].y)==0 && sgn(ps[cur].x,ps[i].x)>0))
cur=i;
swap(ps[cur],ps[0]);
sort(ps+1,ps+n,cmp);
tb[0]=ps[0],tb[1]=ps[1],tb[2]=ps[2];
for(int i=3;i<n;i++)
{
while(sgn(LineSeg(tb[top-1],tb[top])/LineSeg(tb[top-1],ps[i]),0)<0)
top--;
tb[++top]=ps[i];
}
num=top+1;
}
/** 卷包裹法求点集凸壳,参数说明同graham算法 **/
void ConvexClosure(Point ps[],Point tb[],int n,int &num)
{
LineSeg lx,ly;
int cur,ch;
bool vis[Max];
num=-1,cur=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<n;i++)
if(sgn(ps[cur].y,ps[i].y)>0 || (sgn(ps[cur].y,ps[i].y)==0 && sgn(ps[cur].x,ps[i].x)>0))
cur=i;
tb[++num]=ps[cur];
lx.s=Point(ps[cur].x-1,ps[cur].y),lx.e=ps[cur];
/// 选取与最后一条确定边夹角最小的点,即余弦值最大者
while(1)
{
double mxcross=-2,midis,tmxcross;
ly.s=lx.e;
for(int i=0;i<n;i++)if(!vis[i])
{
ly.e=ps[i];
tmxcross=(lx*ly)/lx.lenth()/ly.lenth();
if(sgn(tmxcross,mxcross)>0 ||(sgn(tmxcross,mxcross)==0 && getdis(ly.s,ly.e)<midis))
mxcross=tmxcross,midis=getdis(ly.s,ly.e),ch=i;
}
if(ch==cur)break;
tb[++num]=ps[ch],vis[ch]=1;
lx.s=tb[num-1],lx.e=tb[num],ly.s=tb[num];
}
}
weeping专用模板--更新中
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。