没有合适的资源?快使用搜索试试~ 我知道了~
首页ACM竞赛算法模板:计算几何与数论
ACM竞赛算法模板:计算几何与数论
![](https://csdnimg.cn/release/wenkucmsfe/public/img/star.98a08eaa.png)
"ACM模板包含了ACM竞赛中常用的算法和数据结构模板,涵盖了计算几何、组合数学和数论等多个方面,旨在帮助参赛者快速解决各种问题。" 在ACM(国际大学生程序设计竞赛)中,拥有一个良好的算法模板库是至关重要的。这个模板集合主要分为几个部分: 1. 计算几何:这部分包括了基本的几何概念和公式,如点、线、多边形的处理,以及浮点函数、面积计算、球面几何、三角形和三维几何等。例如,模板中提供了最小圆覆盖、直线旋转、多边形重心、球面距离计算、多边形切割等实用算法,这些都是解决几何问题的基础。 2. 组合数学:组合公式和排列组合的生成是组合数学的核心,用于处理计数问题。模板提供了组合的计算方法、Gray码生成、Polya计数(置换)以及字典序的全排列和组合,这些都是解决复杂组合问题的工具。 3. 数论:在ACM竞赛中,数论算法常常用于解决素数检测、模线性方程组求解、计算阶乘的最后非零位等问题。模板中包含了素数判定、欧拉函数以及高精度计算的相关方法,这些都是处理数论问题的关键。 每个算法模板都伴随着具体的代码示例,比如求解多边形的重心、判断是否存在平面将点集分开、计算线段围成区域的储水量等,这些代码可以直接应用于实际题目中,提高了编程效率。 ACM模板的全面性和实用性使得参赛者能够在面对复杂问题时有现成的解决方案作为参考,从而节省时间,提高解题速度。对于准备ACM比赛或提升编程技能的学生来说,这是一个宝贵的资源,能帮助他们更好地理解和应用算法,解决实际问题。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/2316664/bg10.jpg)
Acm 常用算法模板
16
if (xmult(l.a,t,p)*xmult(l.b,t,p)>eps)
return distance(p,l.a)<distance(p,l.b)?l.a:l.b;
return intersection(p,t,l.a,l.b);
}
point ptoseg(point p,point l1,point l2){
point t=p;
t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;
if (xmult(l1,t,p)*xmult(l2,t,p)>eps)
return distance(p,l1)<distance(p,l2)?l1:l2;
return intersection(p,t,l1,l2);
}
//点到线段距离
double disptoseg(point p,line l){
point t=p;
t.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;
if (xmult(l.a,t,p)*xmult(l.b,t,p)>eps)
return distance(p,l.a)<distance(p,l.b)?distance(p,l.a):distance(p,l.b);
return fabs(xmult(p,l.a,l.b))/distance(l.a,l.b);
}
double disptoseg(point p,point l1,point l2){
point t=p;
t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;
if (xmult(l1,t,p)*xmult(l2,t,p)>eps)
return distance(p,l1)<distance(p,l2)?distance(p,l1):distance(p,l2);
return fabs(xmult(p,l1,l2))/distance(l1,l2);
}
//矢量 V 以 P 为顶点逆时针旋转 angle 并放大 scale 倍
point rotate(point v,point p,double angle,double scale){
point ret=p;
v.x-=p.x,v.y-=p.y;
p.x=scale*cos(angle);
p.y=scale*sin(angle);
ret.x+=v.x*p.x-v.y*p.y;
ret.y+=v.x*p.y+v.y*p.x;
return ret;
}
//p 点关于直线 L 的对称点
ponit symmetricalPointofLine(point p, line L)
{
point p2;
double d;
![](https://csdnimg.cn/release/download_crawler_static/2316664/bg11.jpg)
Acm 常用算法模板
17
d = L.a * L.a + L.b * L.b;
p2.x = (L.b * L.b * p.x - L.a * L.a * p.x -
2 * L.a * L.b * p.y - 2 * L.a * L.c) / d;
p2.y = (L.a * L.a * p.y - L.b * L.b * p.y -
2 * L.a * L.b * p.x - 2 * L.b * L.c) / d;
return p2;
}
//求两点的平分线
line bisector(point& a, point& b) {
line ab, ans; ab.set(a, b);
double midx = (a.x + b.x)/2.0, midy = (a.y + b.y)/2.0;
ans.a = -ab.b, ans.b = -ab.a, ans.c = -ab.b * midx + ab.a * midy;
return ans;
}
// 已知入射线、镜面,求反射线。
// a1,b1,c1 为镜面直线方程(a1 x + b1 y + c1 = 0 ,下同)系数;
a2,b2,c2 为入射光直线方程系数;
a,b,c 为反射光直线方程系数.
// 光是有方向的,使用时注意:入射光向量:<-b2,a2>;反射光向量:<b,-a>.
// 不要忘记结果中可能会有"negative zeros"
void reflect(double a1,double b1,double c1,double a2,double b2,double c2,double &a,double &b,double &c)
{
double n,m;
double tpb,tpa;
tpb=b1*b2+a1*a2;
tpa=a2*b1-a1*b2;
m=(tpb*b1+tpa*a1)/(b1*b1+a1*a1);
n=(tpa*b1-tpb*a1)/(b1*b1+a1*a1);
if(fabs(a1*b2-a2*b1)<1e-20)
{
a=a2;b=b2;c=c2;
return;
}
double xx,yy; //(xx,yy)是入射线与镜面的交点。
xx=(b1*c2-b2*c1)/(a1*b2-a2*b1);
yy=(a2*c1-a1*c2)/(a1*b2-a2*b1);
a=n;
b=-m;
c=m*yy-xx*n;
}
![](https://csdnimg.cn/release/download_crawler_static/2316664/bg12.jpg)
Acm 常用算法模板
18
1.6 面积
#include <math.h>
struct point{double x,y;};
//计算 cross product (P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double xmult(double x1,double y1,double x2,double y2,double x0,double y0){
return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}
//计算三角形面积,输入三顶点
double area_triangle(point p1,point p2,point p3){
return fabs(xmult(p1,p2,p3))/2;
}
double area_triangle(double x1,double y1,double x2,double y2,double x3,double y3){
return fabs(xmult(x1,y1,x2,y2,x3,y3))/2;
}
//计算三角形面积,输入三边长
double area_triangle(double a,double b,double c){
double s=(a+b+c)/2;
return sqrt(s*(s-a)*(s-b)*(s-c));
}
//计算多边形面积,顶点按顺时针或逆时针给出
double area_polygon(int n,point* p){
double s1=0,s2=0;
int i;
for (i=0;i<n;i++)
s1+=p[(i+1)%n].y*p[i].x,s2+=p[(i+1)%n].y*p[(i+2)%n].x;
return fabs(s1-s2)/2;
}
1.7 球面
#include <math.h>
const double pi=acos(-1);
//计算圆心角 lat 表示纬度,-90<=w<=90,lng 表示经度
//返回两点所在大圆劣弧对应圆心角,0<=angle<=pi
![](https://csdnimg.cn/release/download_crawler_static/2316664/bg13.jpg)
Acm 常用算法模板
19
double angle(double lng1,double lat1,double lng2,double lat2){
double dlng=fabs(lng1-lng2)*pi/180;
while (dlng>=pi+pi)
dlng-=pi+pi;
if (dlng>pi)
dlng=pi+pi-dlng;
lat1*=pi/180,lat2*=pi/180;
return acos(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2));
}
//计算距离,r 为球半径
double line_dist(double r,double lng1,double lat1,double lng2,double lat2){
double dlng=fabs(lng1-lng2)*pi/180;
while (dlng>=pi+pi)
dlng-=pi+pi;
if (dlng>pi)
dlng=pi+pi-dlng;
lat1*=pi/180,lat2*=pi/180;
return r*sqrt(2-2*(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2)));
}
//计算球面距离,r 为球半径
inline double sphere_dist(double r,double lng1,double lat1,double lng2,double lat2){
return r*angle(lng1,lat1,lng2,lat2);
}
1.8 三角形
#include <math.h>
struct point{double x,y;};
struct line{point a,b;};
double distance(point p1,point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
point intersection(line u,line v){
point ret=u.a;
double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))
/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
ret.x+=(u.b.x-u.a.x)*t;
ret.y+=(u.b.y-u.a.y)*t;
return ret;
}
![](https://csdnimg.cn/release/download_crawler_static/2316664/bg14.jpg)
Acm 常用算法模板
20
//外心
point circumcenter(point a,point b,point c){
line u,v;
u.a.x=(a.x+b.x)/2;
u.a.y=(a.y+b.y)/2;
u.b.x=u.a.x-a.y+b.y;
u.b.y=u.a.y+a.x-b.x;
v.a.x=(a.x+c.x)/2;
v.a.y=(a.y+c.y)/2;
v.b.x=v.a.x-a.y+c.y;
v.b.y=v.a.y+a.x-c.x;
return intersection(u,v);
}
//内心
point incenter(point a,point b,point c){
line u,v;
double m,n;
u.a=a;
m=atan2(b.y-a.y,b.x-a.x);
n=atan2(c.y-a.y,c.x-a.x);
u.b.x=u.a.x+cos((m+n)/2);
u.b.y=u.a.y+sin((m+n)/2);
v.a=b;
m=atan2(a.y-b.y,a.x-b.x);
n=atan2(c.y-b.y,c.x-b.x);
v.b.x=v.a.x+cos((m+n)/2);
v.b.y=v.a.y+sin((m+n)/2);
return intersection(u,v);
}
//垂心
point perpencenter(point a,point b,point c){
line u,v;
u.a=c;
u.b.x=u.a.x-a.y+b.y;
u.b.y=u.a.y+a.x-b.x;
v.a=b;
v.b.x=v.a.x-a.y+c.y;
v.b.y=v.a.y+a.x-c.x;
return intersection(u,v);
}
剩余223页未读,继续阅读
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)