杭州电子科技大学ACM集训队资料集杭州电子科技大学ACM集训队资料集
杭州电子科技大学ACM集训队资料集
2005.11
Contents
一 Acm比赛注意事项 …………………………………………… 02
二 Numbers和数学公式 ………………………………………… 05
三 数论模板 ……………………………………………………….. 08
四 大数类 ………………………………………………………….. 10
五 计算几何模板 ………………………………………………….. 14
六 经典算法和源码 ……………………………………………….. 27 ...
杭州电子科技大学ACM集训队资料集
杭州电子科技大学ACM集训队资料集
2005.11
Contents
一 Acm比赛注意事项 …………………………………………… 02
二 Numbers和数学公式 ………………………………………… 05
三 数论模板 ……………………………………………………….. 08
四 大数类 ………………………………………………………….. 10
五 计算几何模板 ………………………………………………….. 14
六 经典算法和源码 ……………………………………………….. 27
1128_求矩形面积和_线段树 ………………….. 27
匈牙利算法1525 ……………………………….. 31
最大子段和 ……………………………………... 32
字典树 …………………………………………... 35
1203_kruscal …………………………………... 37
1203_prim ………………………………………. 40
Dijkstra ………………………………………….. 43
Bellman—ford ………………………………….. 45
七 线性规划...............................................................................67
八 高斯消元...............................................................................69
九 图论相关算法........................................................................74
十 三角函数表............................................................................84
1
杭州电子科技大学ACM集训队资料集
Acm比赛注意事项
1. 服务器不支持long double类型,最高支持到double(浮点型)和long long
(长整型),注意 double 比float 更适宜。
2. while语句中的(cin>>M>>N && M!=0 && N!=0)(注意是与还是或)上式也
可改写成(cin>>M>>N && (M || N))
3. 在有些题目,特别是数据比较烦的时候,或者数据精度要求高的时候,可能
精度要求不够。。。
,m=1; for(i=1; i<=k; 4. (引用其他人的)奇怪的事情多着呢.昨天我做2305时候
i++) m *= 2和 m = (1<
>n && n!=-1)
{ ... }
则会出错,而应该
while(cin>>n && n > 0)
{ ... }
这是在zoj_1475中的一个陷阱。
16. 打开文件的语句别写错了,还有文件名小心郁闷死你.多注意点细节,不要频繁提交。
常用的词汇(如max,min)作为变量名在本地机上可以正常编译,但递交上17. 一些
去不一定能编译.更郁闷的是用了一些常用的词汇,编译也通过了,输出答案也是正确的,但就是wa.解决:单词前面加上一个字母,比如lmax,lmin
18. 当提交一直WA时,再仔细读一边题目,而不是一味的想特殊数据。
19. 关于比赛配合问题:1) 拿到题目一般是每人看几道题..也就是扫描一下输入输出什么的,简单讨论一下确定出一道最简单的让一个人去做,机子空着毕竟比较浪费...剩下两个人就可以把题目熟悉起来了...三个人讨论题目的话机子又空着了~~呵呵,一般两个人讨论就行了. 2) 开始地时候三个人分工好每人看几道题,第一时间找到最简单地题,然后一个人开始写程序,另外两个人开始讨论剩下的题目,按照难度/可能通过率/熟悉程度/决定下面做那些题目,然后在纸上写程序,调试. 3) 还有随时注意观察其他队的动态如果有的题目大多数队都通过了而自己还没有做的话,赶快做这个题目。或者是自己一个题目做了很久没有通过,而其他队也没有通过的话,很有可能就是数据有问题或者题目有陷阱,赶快换题目做。比赛不是比谁能做出难题,而是谁能做出更多的题目。
4
杭州电子科技大学ACM集训队资料集
Numbers和数学公式
一. Fibonacci Number
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 …
二. Lucas Number (特殊的Fibonacci Number )
1, 3, 4, 7, 11, 18, 29, 47, 76, 123 , ...
三. Catalan Number
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845, …
计算公式: C(2n, n) / (n + 1)
应用:
1. 将 n + 2 边形沿弦切割成 n个三角形的不同切割数
2. n +,个数相乘,给每两个元素加上括号的不同方法数
eg: n = 2: (1 (2 3)) , ((1 2) 3)
n = 3: (1 (2 (3 4))), (1 ((2 3) 4)) , ((1 2) (3 4)), ((1 (2 3)) 4), (((1 2) 3) 4)
3. the number of rooted, trivalent trees with n + 1 nodes
eg: n = 2
n = 3
4. the number of paths of length 2n through an n-by-n grid that do not rise above
the main diagonal(对角线).
5
杭州电子科技大学ACM集训队资料集
eg: n = 2
n = 3
5. 结点数为 n 的二叉树的不同构造数.
四. striling number(斯特灵数)
1, 3 , 13, 75, 541, 4683, 47293, 545835, 7087261,
102247563 …
构造法:
n个有标号的球放到m 个无标号的盒子中,要求无一为空,其不同的方案数
记作: s(n,m)
s(0,0) = 0, s(n,k)=0 (n1,m>=1)
五. bell number (和striling number 相似)
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975,…
定义:
N元集合的所有划分数称为Bell数,
记做Bn,根据第二类Stirling数的意义,我们可以很容易的得到:
Bn=sigma(S(n,k)) (k=1,2…n) // sigma求和
六. 杨式图表的个数
杨式图表(Young Tableau)是一个矩阵,它满足条件:
如果格子(i , j)没有元素,则它右边和上边的相邻格子也一定没有元素。
如果格子(i , j)有元素a[i,j],则它右边和上边的相邻格子要么没有元素,要么比a[i,j]
大。
1 ~ n 所组成的杨式图表的个数由下式给出:
a(1) = 1, a(2) = 2
a(n) = a(n-1) + (n-1) * a(n-2) (n>2)
6
杭州电子科技大学ACM集训队资料集
上图为n = 3 的 杨式图表
七 钩子公式
对于给定形状,不同的杨式图表的个数为n! 除以每个格子的钩子长度加1的积。
其中,钩子长度定义为该格子右边的格子数和它上面的格子数子和。
八. 三角形内切圆半径
s=(a+b+c)/2
九. 三角形外接圆半径
r =(a*b*c)/(4*s) 其中s为三角形面积。
十. 圆內接四边形面积公式
圆內接四边形,其四边边长分別为a,b,c,d 。
令 s=(a+b+c+d) / 2,则四边行面积为
sqrt( (s-a)*(s-b)*(s-c)*(s-d) )
7
杭州电子科技大学ACM集训队资料集
数论模板
int gcd(int a, int b)//最大公约数
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
//扩展的欧拉函数,返回放在x, y中
// d = gcd(a, b) 这里求得的x, y满足 d = ax + by int extend_euclid(int a,int b,int &x,int &y)
{
int t,d;
if (b==0) {x=1;y=0;return a;}
d=extend_euclid(b,a %b,x,y);
t=x;
x=y;
y=t-a/b*y;
return d;
}
//求解同余方程ax=b(mod n)
void linear_solve(int a, int b, int n)
{
int d, x, y;
d = extend_euclid(a, n, x, y);//调用扩展的欧拉函数
if(b%d==0)
{
int e = (x*(b/d))%n;//e等于x0
int ans = n;
for(int i=0; i
#include
#include
const bool SafeFirst=false; //一般当同时使用了两个或两个以上大数运算时应设置为true;设置安全优先还是效率优先.若效率优先(false),一定要保证传入到函数中的数据都是规格的大数,否则可能出错.效率差常数倍,一般是1倍,要看具体数据,数据越小,而lmax开得越大,差距越大.一般建议用true const int nw=8; //jz中0的个数,nw<=8
const int jz=100000000; //配置进制,只能是10^nw
const int lmax=100000; //大数数组开的大小,(lmax-1)*nw为大数的位数
void jia(const int a[],const int b[],int c[]) //大数a[]加大数b[],结果存在c[]中 {
int i,top;
top=a[0]>b[0]?a[0]:b[0];
if (SafeFirst) //在false情况下,如果传入的c[]非规格的,不能保证返回的c[]规格
{
memset(c,0,sizeof(int)*lmax);
}else
10
杭州电子科技大学ACM集训队资料集
{
c[top+1]=0;
}
for (i=1;i<=top;i++)
{
c[i]+=a[i]+b[i];
if (c[i]>=jz)
{
c[i]-=jz;
c[i+1]++;
}
}
if (c[top+1]>0)
c[0]=top+1;
else
c[0]=top;
}
void jia2(int a[],const int b[]) //对大数a[]累加另一大数b[] {
int i,top;
if (SafeFirst)
memset(a+a[0]+1,0,sizeof(int)*(lmax-a[0]-1));
top=a[0]>b[0]?a[0]:b[0];
for (i=1;i<=b[0];i++)
{
a[i]+=b[i];
if (a[i]>=jz)
{
a[i]-=jz;
a[i+1]++;
}
}
if (a[top+1]>0)
a[0]=top+1;
else
a[0]=top;
}
void jia3(const int a[],const int b,int c[]) //大数a[]加上小数b,存在c[]中
{
int i;
unsigned int t;
if (SafeFirst) memset(c,0,sizeof(int)*lmax);
memcpy(c,a,sizeof(int)*(a[0]+1));
t=c[1]+b;
11
杭州电子科技大学ACM集训队资料集
c[1]=t%jz;
i=1;
while (t>=jz)
{
t/=jz;
t+=c[i+1];
c[i+1]=t%jz;
i++;
}
if (c[0]=jz)
{
t/=jz;
t+=a[i+1];
a[i+1]=t%jz;
i++;
}
if (a[0]=b[]
{
int i,jw;
if (SafeFirst) //若为false,不能保证传出的c[]是规格的
{
memset(c,0,sizeof(int)*lmax);
}
jw=0;
for (i=1;i<=b[0];i++)
{
if (a[i]-jw>=b[i])
12
杭州电子科技大学ACM集训队资料集
{
c[i]=a[i]-jw-b[i];
jw=0;
}
else
{
c[i]=a[i]+jz-jw-b[i];
jw=1;
}
}
for (i=b[0]+1;i<=a[0];i++)
{
if (a[i]-jw>=0)
{
c[i]=a[i]-jw;
jw=0;
}else
{
c[i]=a[i]+jz-jw;
jw=1;
}
}
i=a[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void jian2(int a[],const int b[]) //a[]-=b[];a[]>b[]
{
int i;
if (SafeFirst) memset(&a[a[0]+1],0,sizeof(int)*(lmax-a[0]-1));
for (i=1;i<=b[0];i++)
{
a[i]-=b[i];
if (a[i]<0)
{
a[i]+=jz;
a[i+1]--;
}
}
while (a[i]<0 && i0) a[0]=i;
else a[0]=1;
}
void jian3(const int a[],const int b,int c[]) //a[]>=b
{
int i;
memcpy(c,a,sizeof(int)*(a[0]+1));
if (SafeFirst) memset(&c[c[0]+1],0,sizeof(int)*(lmax-a[0]-1));
c[1]-=b;
i=1;
while (c[i]<0)
{
c[i+1]+=c[i]/jz;
c[i]%=jz;
if (c[i]<0)
{
c[i+1]--;
c[i]+=jz;
}
i++;
}
i=c[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void jian4(int a[],const int b)
{
int i;
a[1]-=b;
i=1;
while (a[i]<0)
{
a[i+1]+=a[i]/jz;
a[i]%=jz;
if (a[i]<0)
{
14
杭州电子科技大学ACM集训队资料集
a[i+1]--;
a[i]+=jz;
}
i++;
}
i=a[0];
while (a[i]==0) i--;
if (i>0) a[0]=i;
else
a[0]=1;
}
/********************************************************************
***************************/
inline void chen(const int a[],const int b[],int c[]) //大数乘大数 {
__int64 t=0;
int up=0,i,j,k;
if (SafeFirst)
memset(c,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i++)
{
up=0;
for (j=1;j<=b[0];j++)
{
k=i+j-1;
t=(__int64)a[i]*b[j]+up;
c[k]+=t%jz;
up=t/jz;
while (c[k]>=jz)
{
c[k+1]++;
c[k]-=jz;
}
}
if (up>0)
{
c[i+b[0]]+=up;
}
}
i=a[0]+b[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
15
杭州电子科技大学ACM集训队资料集
else
c[0]=1;
}
inline void chen2(const int a[],const int b,int c[]) //大数乘小数{
__int64 t;
int up=0,i;
if (SafeFirst)
memset(c,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i++)
{
t=(__int64)a[i]*b+up;
c[i]=t%jz;
up=t/jz;
}
c[i]+=up;
while (c[i]>=jz)
{
c[i+1]=c[i]/jz;
c[i]%=jz;
i++;
}
if (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
/********************************************************************
***************************/ void chghtl(const int a[],int b[])
{
int t,i,j,p=0;
memset(b,0,sizeof(int)*nw*lmax);
for (i=1;i<=a[0];i++)
{
t=a[i];
for (j=1;j<=nw;j++)
{
p++;
b[p]=t%10;
t/=10;
}
16
杭州电子科技大学ACM集训队资料集
}
while (b[p]==0) p--;
if (p>0) b[0]=p;
else b[0]=1;
}
void chglth(const int a[],int b[]) {
int i,j,top;
memset(b,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i+=nw)
{
b[0]++;
top=i+nw-1;
if (top>a[0]) top=a[0];
for (j=top;j>=i;j--)
{
b[b[0]]=b[b[0]]*10+a[j];
}
}
}
void chu(int a[],const int b[],int c[]) //c[]=a[]%b[],a[]/=b[];a[]>=0 && b[]>0;
{
int *a1=new int[nw*lmax],*b1=new int[nw*lmax],*c1=new
int[nw*lmax],i,j,lcount;
bool ok;
memset(a1,0,sizeof(int)*nw*lmax);
memset(b1,0,sizeof(int)*nw*lmax);
memset(c1,0,sizeof(int)*nw*lmax);
chghtl(a,a1);
chghtl(b,b1);
for (i=a1[0];i>=b1[0];i--)
{
if (i=1;j--)
if (a1[i+j-b1[0]]b1[j])
17
杭州电子科技大学ACM集训队资料集
{
ok=true;
break;
}
lcount=0;
while (ok)
{
for (j=1;j<=b1[0];j++)
{
a1[i+j-b1[0]]-=b1[j];
if (a1[i+j-b1[0]]<0)
{
a1[i+j-b1[0]]+=10;
a1[i+j-b1[0]+1]--;
}
}
lcount++;
) for (j=b1[0];j>=1;j--
if (a1[i+j-b1[0]]b1[j])
{
ok=true;
break;
}
}
c1[i-b1[0]+1]=lcount;
}
i=a1[0];
while (c1[i]==0) i--;
if (i>0) c1[0]=i;
else
c1[0]=1;
i=b1[0];
while (a1[i]==0) i--;
if (i>0) a1[0]=i;
else
a1[0]=1;
for (i=1;i<=a1[0];i++)
if (a1[i]>9)
{
a1[i+1]+=a1[i]/10;
18
杭州电子科技大学ACM集训队资料集
a1[i]%=10;
}
while (a1[i]>9)
{
a1[i+1]=a1[i]/10;
a1[i]%=10;
i++;
}
if (a1[i]==0) i--;
if (i>0) a1[0]=i;
else
a1[0]=1;
chglth(a1,c);
chglth(c1,a);
delete []a1;
delete []b1;
delete []c1;
}
void chu2(const int a[],const int b[],int c[], int d[]) //c[]=a[]/b[];d[]=a[]%b[]
{
memcpy(c,a,sizeof(int)*lmax);
chu(c,b,d);
}
void chu3(int a[],const int b,int c[]) //c[]=a[]%b; a[]/=b;
{
__int64 t;
int i;
memcpy(c,a,sizeof(int)*lmax);
for (i=c[0];i>=1;i--)
{
if (i0) a[0]=i;
else
a[0]=1;
i=1;
while (c[i]>=jz)
{
c[i+1]=c[i]/jz;
c[i]%=jz;
i++;
}
if (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void chu4(const int a[],const int b,int c[],int d[]) //c[]=a[]/b; d[]=a[]%b;
{
memcpy(c,a,sizeof(int)*lmax);
chu3(c,b,d);
}
/********************************************************************
***************************/
void chgstn(const char s[],int a[]) //字符串转大数 {
int i,t1,l,j,t;
memset(a,0,sizeof(a));
l=strlen(s);
for (i=l-1;i>=0;i-=nw)
{
t=0;
t1=i-nw+1;
if (t1<0) t1=0;
for (j=t1;j<=i;j++)
t=t*10+s[j]-'0';
a[0]++;
a[a[0]]=t;
}
}
void output(const int c[]) //大数输出
{
int i,w,j,n;
20
杭州电子科技大学ACM集训队资料集
printf("%d",c[c[0]]);
for (i=c[0]-1;i>0;i--)
{
n=c[i];
w=0;
while (n>0)
{
w++;
n/=10;
}
for (j=0;j0) printf("%d",c[i]);
}
printf("\n");
}
void jiecheng(int n=-1) {
int begin,i,cost,*t=new int[lmax],*a=new int[lmax];
memset(t,0,sizeof(t)*lmax);
memset(a,0,sizeof(a)*lmax);
if (n<0)
scanf("%d",&n);
begin=time(0);
a[0]=1;
a[1]=1;
for (i=2;i<=n;i++)
{
for (int j=1;j<=a[0];j++)
t[j]=a[j];
t[0]=a[0];
chen2(t,i,a);
}
cost=time(0)-begin;
output(a);
printf("Cost time : %d\n",cost);
delete []t;
delete []a;
}
void chenfang(const int a[],int n,int c[]) //求a[]的n次方 {
int i,*b=new int[lmax];
memcpy(b,a,sizeof(int)*lmax);
memcpy(c,a,sizeof(int)*lmax);
21
杭州电子科技大学ACM集训队资料集
for (i=2;i<=n;i++)
{
chen(b,a,c);
memcpy(b,c,sizeof(int)*lmax);
}
delete []b;
}
void examinechenfang() //检测chenfang()的正确性 {
int a[lmax]={0},b[lmax]={0},n;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
chenfang(a,n,b);
output(b);
}
}
void examinejia()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
}
}
void examinejia2()
{
int a[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
22
杭州电子科技大学ACM集训队资料集
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
jia2(c,a);
}
output(c);
}
}
void examinejia3()
{
int a[lmax],b,c[lmax],n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
// memset(c,0,sizeof(c));
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(c);
}
}
void examinejia4()
{
int a[lmax],b,n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia4(a,b);
}
output(a);
}
}
void examinejian()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
23
杭州电子科技大学ACM集训队资料集
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(c));
jian(b,a,c);
}
output(c);
}
}
void examinejian2()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
for (i=1;i<=n;i++)
{
jian2(c,a);
}
output(c);
}
}
void examinejian3()
{
int a[lmax],b,c[lmax],n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
24
杭州电子科技大学ACM集训队资料集
{
// memset(c,0,sizeof(c));
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(a);
for (i=1;i<=n;i++)
{
jian3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(a);
}
}
void examinejian4() {
int a[lmax],b,n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia4(a,b);
}
output(a);
for (i=1;i<=n;i++)
{
jian4(a,b);
}
output(a);
}
}
void examinechu()
{
int a[lmax],b[lmax],c[lmax];
char s[lmax*nw];
while (scanf("%s",s))
{
chgstn(s,a);
scanf("%s",s);
25
杭州电子科技大学ACM集训队资料集
chgstn(s,b);
chu(a,b,c);
output(a);
output(c);
}
}
void examinechu2() {
int a[lmax],b[lmax],c[lmax],d[lmax];
char s[lmax*nw];
while (scanf("%s",s)!=EOF)
{
chgstn(s,a);
scanf("%s",s);
chgstn(s,b);
chu2(a,b,c,d);
output(c);
output(d);
}
}
void examinechu4() {
int a[lmax],c[lmax],d[lmax],b;
char s[nw*lmax];
while (scanf("%s%d",s,&b)!=EOF)
{
chgstn(s,a);
chu4(a,b,c,d);
output(c);
output(d);
}
}
int main()
{
// 以下用来检测各函数的正确性
jiecheng();
// examinechenfang(); // examinejia(); // examinejia2(); // examinejia3(); // examinejia4(); // examinejian(); // examinejian2(); // examinejian3();
26
杭州电子科技大学ACM集训队资料集 // examinejian4();
// examinechu();
// examinechu2();
// examinechu4();
return 0;
}
取模.cpp
int div(char *A,int B)
{
int I;
int C = 0;
int Alen=strlen(A);
for (I = 0; I
#include
#include
#include
#include
#include
using namespace std;
typedef double TYPE;
#define Abs(x) (((x)>0)?(x):(-(x))) #define Sgn(x) (((x)<0)?(-1):(1)) #define Max(a,b) (((a)>(b))?(a):(b)) #define Min(a,b) (((a)<(b))?(a):(b))
#define Epsilon 1e-10
#define Infinity 1e+10
#define Pi 3.14159265358979323846
TYPE Deg2Rad(TYPE deg)
{
return (deg * Pi / 180.0); }
TYPE Rad2Deg(TYPE rad)
{
return (rad * 180.0 / Pi); }
28
杭州电子科技大学ACM集训队资料集 TYPE Sin(TYPE deg)
{
return sin(Deg2Rad(deg));
}
TYPE Cos(TYPE deg)
{
return cos(Deg2Rad(deg));
}
TYPE ArcSin(TYPE val)
{
return Rad2Deg(asin(val));
}
TYPE ArcCos(TYPE val)
{
return Rad2Deg(acos(val));
}
TYPE Sqrt(TYPE val)
{
return sqrt(val);
}
struct POINT
{
TYPE x;
TYPE y;
TYPE z;
POINT() : x(0), y(0), z(0) {};
POINT(TYPE _x_, TYPE _y_, TYPE _z_ = 0) : x(_x_), y(_y_), z(_z_) {};
};
// cross product of (o->a) and (o->b) // 叉乘
TYPE Cross(const POINT & a, const POINT & b, const POINT & o) {
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
// planar points' distance // 两个点的距离
TYPE Distance(const POINT & a, const POINT & b)
29
杭州电子科技大学ACM集训队资料集 {
return Sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) +
(a.z - b.z) * (a.z - b.z)); }
struct LINE
{
POINT a;
POINT b;
LINE() {};
LINE(POINT _a_, POINT _b_) : a(_a_), b(_b_) {};
};
// 返回直线 Ax + By + C =0 的系数
void Coefficient(const LINE & L, TYPE & A, TYPE & B, TYPE & C)
{
A = L.b.y - L.a.y;
B = L.a.x - L.b.x;
C = L.b.x * L.a.y - L.a.x * L.b.y; }
void Coefficient(const POINT & p,const TYPE a,TYPE & A,TYPE & B,TYPE & C)
{
A = Cos(a);
B = Sin(a);
C = - (p.y * B + p.x * A); }
// 线段
struct SEG
{
POINT a;
POINT b;
SEG() {};
SEG(POINT _a_, POINT _b_):a(_a_),b(_b_) {};
};
// 圆
struct CIRCLE
{
TYPE x;
TYPE y;
TYPE r;
CIRCLE() {}
30
杭州电子科技大学ACM集训队资料集
CIRCLE(TYPE _x_, TYPE _y_, TYPE _r_) : x(_x_), y(_y_), r(_r_) {}
};
POINT Center(const CIRCLE & circle)
{
return POINT(circle.x, circle.y);
}
TYPE Area(const CIRCLE & circle)
{
return Pi * circle.r * circle.r;
}
//两个圆的公共面积
TYPE CommonArea(const CIRCLE & A, const CIRCLE & B)
{
TYPE area = 0.0;
const CIRCLE & M = (A.r > B.r) ? A : B;
const CIRCLE & N = (A.r > B.r) ? B : A;
TYPE D = Distance(Center(M), Center(N));
if ((D < M.r + N.r) && (D > M.r - N.r))
{
TYPE cosM = (M.r * M.r + D * D - N.r * N.r) / (2.0 * M.r * D);
TYPE cosN = (N.r * N.r + D * D - M.r * M.r) / (2.0 * N.r * D);
TYPE alpha = 2.0 * ArcCos(cosM);
TYPE beta = 2.0 * ArcCos(cosN);
TYPE TM = 0.5 * M.r * M.r * Sin(alpha);
TYPE TN = 0.5 * N.r * N.r * Sin(beta);
TYPE FM = (alpha / 360.0) * Area(M);
TYPE FN = (beta / 360.0) * Area(N);
area = FM + FN - TM - TN;
}
else if (D <= M.r - N.r)
{
area = Area(N);
}
return area;
31
杭州电子科技大学ACM集训队资料集 }
// 矩形
//矩形的线段
// 2
// --------------- b
// | |
// 3 | | 1 // a ---------------
// 0
struct RECT
{
POINT a; // 左下点
POINT b; // 右上点
RECT() {};
RECT(const POINT & _a_, const POINT & _b_)
{
a = _a_;
b = _b_;
}
};
//根据下标返回多边形的边
SEG Edge(const RECT & rect, int idx)
{
SEG edge;
while (idx < 0) idx += 4;
switch (idx % 4)
{
case 0:
edge.a = rect.a;
edge.b = POINT(rect.b.x, rect.a.y);
break;
case 1:
edge.a = POINT(rect.b.x, rect.a.y);
edge.b = rect.b;
break;
case 2:
edge.a = rect.b;
edge.b = POINT(rect.a.x, rect.b.y);
break;
case 3:
edge.a = POINT(rect.a.x, rect.b.y);
32
杭州电子科技大学ACM集训队资料集
edge.b = rect.a;
break;
default:
break;
}
return edge;
}
TYPE Area(const RECT & rect)
{
return (rect.b.x - rect.a.x) * (rect.b.y - rect.a.y);
}
// 两个矩形的公共面积
TYPE CommonArea(const RECT & A, const RECT & B) {
TYPE area = 0.0;
POINT LL(Max(A.a.x, B.a.x), Max(A.a.y, B.a.y));
POINT UR(Min(A.b.x, B.b.x), Min(A.b.y, B.b.y));
if ((LL.x <= UR.x) && (LL.y <= UR.y))
{
area = Area(RECT(LL, UR));
}
return area;
}
// 多边形 ,逆时针或顺时针给出x,y
struct POLY
{
int n; //n个点
TYPE * x; //x,y为点的指针,首尾必须重合
TYPE * y;
POLY() : n(0), x(NULL), y(NULL) {};
POLY(int _n_, const TYPE * _x_, const TYPE * _y_)
{
n = _n_;
x = new TYPE[n + 1];
memcpy(x, _x_, n*sizeof(TYPE));
x[n] = _x_[0];
33
杭州电子科技大学ACM集训队资料集
y = new TYPE[n + 1];
memcpy(y, _y_, n*sizeof(TYPE));
y[n] = _y_[0];
}
};
//多边形顶点
POINT Vertex(const POLY & poly, int idx)
{
idx %= poly.n;
return POINT(poly.x[idx], poly.y[idx]); }
//多边形的边
SEG Edge(const POLY & poly, int idx)
{
idx %= poly.n;
return SEG(POINT(poly.x[idx], poly.y[idx]),
POINT(poly.x[idx + 1], poly.y[idx + 1]));
}
//多边形的周长
TYPE Perimeter(const POLY & poly)
{
TYPE p = 0.0;
for (int i = 0; i < poly.n; i++)
p = p + Distance(Vertex(poly, i), Vertex(poly, i + 1));
return p;
}
bool IsEqual(TYPE a, TYPE b)
{
return (Abs(a - b) < Epsilon); }
bool IsEqual(const POINT & a, const POINT & b) {
return (IsEqual(a.x, b.x) && IsEqual(a.y, b.y));
}
bool IsEqual(const LINE & A, const LINE & B)
{
TYPE A1, B1, C1;
34
杭州电子科技大学ACM集训队资料集
TYPE A2, B2, C2;
Coefficient(A, A1, B1, C1);
Coefficient(B, A2, B2, C2);
return IsEqual(A1 * B2, A2 * B1) &&
IsEqual(A1 * C2, A2 * C1) &&
IsEqual(B1 * C2, B2 * C1);
}
// 判断点是否在线段上
bool IsOnSeg(const SEG & seg, const POINT & p)
{
return (IsEqual(p, seg.a) || IsEqual(p, seg.b)) ||
(((p.x - seg.a.x) * (p.x - seg.b.x) < 0 ||
(p.y - seg.a.y) * (p.y - seg.b.y) < 0) &&
(IsEqual(Cross(seg.b, p, seg.a), 0))); }
//判断两条线断是否相交,端点重合算相交
bool IsIntersect(const SEG & u, const SEG & v)
{
return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) >= 0) &&
(Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) >= 0) &&
(Max(u.a.x, u.b.x) >= Min(v.a.x, v.b.x)) &&
(Max(v.a.x, v.b.x) >= Min(u.a.x, u.b.x)) &&
(Max(u.a.y, u.b.y) >= Min(v.a.y, v.b.y)) &&
(Max(v.a.y, v.b.y) >= Min(u.a.y, u.b.y)); }
//判断两条线断是否平行
bool IsParallel(const LINE & A, const LINE & B)
{
TYPE A1, B1, C1;
TYPE A2, B2, C2;
Coefficient(A, A1, B1, C1);
Coefficient(B, A2, B2, C2);
return (A1 * B2 == A2 * B1) &&
((A1 * C2 != A2 * C1) || (B1 * C2 != B2 * C1)); }
//判断两条直线断是否相交
bool IsIntersect(const LINE & A, const LINE & B)
{
35
杭州电子科技大学ACM集训队资料集
return !IsParallel(A, B);
}
//直线相交的交点
POINT Intersection(const LINE & A, const LINE & B)
{
TYPE A1, B1, C1;
TYPE A2, B2, C2;
Coefficient(A, A1, B1, C1);
Coefficient(B, A2, B2, C2);
POINT I(0, 0);
I.x = - (B2 * C1 - B1 * C2) / (A1 * B2 - A2 * B1);
I.y = (A2 * C1 - A1 * C2) / (A1 * B2 - A2 * B1);
return I;
}
bool IsInCircle(const CIRCLE & circle, const RECT & rect)
{
return (circle.x - circle.r >= rect.a.x) &&
(circle.x + circle.r <= rect.b.x) &&
(circle.y - circle.r >= rect.a.y) &&
(circle.y + circle.r <= rect.b.y); }
//判断是否简单多边形
bool IsSimple(const POLY & poly)
{
if (poly.n < 3)
return false;
SEG L1, L2;
for (int i = 0; i < poly.n - 1; i++)
{
L1 = Edge(poly, i);
for (int j = i + 1; j < poly.n; j++)
{
L2 = Edge(poly, j);
if (j == i + 1)
{
if (IsOnSeg(L1, L2.b) || IsOnSeg(L2, L1.a))
return false;
36
杭州电子科技大学ACM集训队资料集
}
else if (j == poly.n - i - 1)
{
if (IsOnSeg(L1, L2.a) || IsOnSeg(L2, L1.b))
return false;
}
else
{
if (IsIntersect(L1, L2))
return false;
}
} // for j
} // for i
return true;
}
//求多边形面积
TYPE Area(const POLY & poly)
{
if (poly.n < 3) return TYPE(0);
double s = poly.y[0] * (poly.x[poly.n - 1] - poly.x[1]);
for (int i = 1; i < poly.n; i++)
{
s += poly.y[i] * (poly.x[i - 1] - poly.x[(i + 1) % poly.n]);
}
return s/2;
}
//判断是否在多边形上
bool IsOnPoly(const POLY & poly, const POINT & p) {
for (int i = 0; i < poly.n; i++)
{
if (IsOnSeg(Edge(poly, i), p))
{
return true;
}
}
return false;
}
//判断是否在多边形内部
bool IsInPoly(const POLY & poly, const POINT & p) {
37
杭州电子科技大学ACM集训队资料集
SEG L(p, POINT(Infinity, p.y));
int count = 0;
for (int i = 0; i < poly.n; i++)
{
SEG S = Edge(poly, i);
if (IsOnSeg(S, p))
{
return false; //如果想让 在poly上则返回 true,
//则改为true
}
if (!IsEqual(S.a.y, S.b.y))
{
POINT & q = (S.a.y > S.b.y)?(S.a):(S.b);
if (IsOnSeg(L, q))
{
++count;
}
else if (!IsOnSeg(L, S.a) && !IsOnSeg(L, S.b) && IsIntersect(S, L))
{
++count;
}
}
}
return (count % 2 != 0);
}
// 点阵的凸包,返回一个多边形
POLY ConvexHull(const POINT * set, int n) // 不适用于点少于三个的情况 {
POINT * points = new POINT[n];
memcpy(points, set, n * sizeof(POINT));
TYPE * X = new TYPE[n];
TYPE * Y = new TYPE[n];
int i, j, k = 0, top = 2;
for(i = 1; i < n; i++)
{
if ((points[i].y < points[k].y) ||
((points[i].y == points[k].y) &&
(points[i].x < points[k].x)))
{
k = i;
38
杭州电子科技大学ACM集训队资料集
}
}
std::swap(points[0], points[k]);
for (i = 1; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if ((Cross(points[j], points[k], points[0]) > 0) ||
((Cross(points[j], points[k], points[0]) == 0) &&
(Distance(points[0], points[j]) < Distance(points[0], points[k]))))
{
k = j;
}
}
std::swap(points[i], points[k]);
}
X[0] = points[0].x; Y[0] = points[0].y;
X[1] = points[1].x; Y[1] = points[1].y;
X[2] = points[2].x; Y[2] = points[2].y;
for (i = 3; i < n; i++)
{
while (Cross(points[i], POINT(X[top], Y[top]),
POINT(X[top - 1], Y[top - 1])) >= 0)
{
top--;
}
++top;
X[top] = points[i].x;
Y[top] = points[i].y;
}
delete [] points;
POLY poly(++top, X, Y);
delete [] X;
delete [] Y;
39
杭州电子科技大学ACM集训队资料集
return poly;
}
从6边长求4面体体积啊
Cayley-Menger Determinant 3 维时的情形(2维相当于海伦公式).
| 0 1 1 1 1 |
| 1 0 D12 D13 D14 |
288*V^2 = | 1 D21 0 D23 D24 |
| 1 D31 D32 0 D34 |
| 1 D41 D42 D43 0 |
其中
V 是四面体的体积.
Dij 是连结顶点i和顶点j的边长的平方(记得是平方).
求球面上两点最短距离模板.cpp
/计算圆心角lat表示纬度,-90<=w<=90,lng表示经度
//返回两点所在大圆劣弧对应圆心角,0<=angle<=pi
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)
40
杭州电子科技大学ACM集训队资料集
{
return r*angle(lng1,lat1,lng2,lat2);
}
射线与三角形所在平面的交点.cpp
//v0,dir为点和方向。p1,p2,p3为三角形
//nor为交点
//最后5行判断交点是否在三角形内
int occluded(double v0[],double dir[],double p1[],double p2[],double p3[])
{
double v1[]={p2[0]-p1[0],p2[1]-p1[1],p2[2]-p1[2]};
double v2[]={p3[0]-p2[0],p3[1]-p2[1],p3[2]-p2[2]};
double nor[3];
double a,b;
double area1,area2,area3,area4;
crossproduct(nor,v1,v2);
b=(v0[0]-p1[0])*nor[0]+(v0[1]-p1[1])*nor[1]+(v0[2]-p1[2])*nor[2];
a=dir[0]*nor[0]+dir[1]*nor[1]+dir[2]*nor[2];
if (fabs(a)area4+inf) return 0;
return 1;
}
41
杭州电子科技大学ACM集训队资料集
以知三点求圆心坐标.cpp
double GetRadiusBy3Points( double x1 , double y1 ,
double x2 , double y2 ,
double x3 , double y3 ,
double &x , double &y ) {
//由 ( x - x1 )^2 + ( y - y1 )^2 = ( x - x2 )^2 + ( y - y2 )^2 得
//2*( x2 - x1 )*x + 2*( y2 - y1 )*y = x2^2 - x1^2 + y2^2 - y1^2
//同理得
//2*( x3 - x2 )*x + 2*( y3 - y2 )*y = x3^2 - x2^2 + y3^2 - y2^2
//由行列式解方程得 x , y
double a11 , a12 , a21 , a22 , b1 , b2 ;
double d , d1 , d2 ;
a11 = 2 * ( x3 - x2 ) ;
a12 = 2 * ( y3 - y2 ) ;
a21 = 2 * ( x2 - x1 ) ;
a22 = 2 * ( y2 - y1 ) ;
b1 = x3*x3 - x2*x2 + y3*y3 - y2*y2 ;
b2 = x2*x2 - x1*x1 + y2*y2 - y1*y1 ;
d = a11*a22 - a12*a21 ;
d1 = b1*a22 - a12*b2 ;
d2 = a11*b2 - b1*a21 ;
// x , y 是圆心坐标
x = d1 / d ;
y = d2 / d ;
return (x1 - x)*(x1 - x) + (y1 - y)*(y1 - y) ; }
42
杭州电子科技大学ACM集训队资料集
点到直线距离
#include
#include
using namespace std;
double RtnDistance(double x1,double y1,double x2,double y2,double px,double py)
{
const double minjd=0.001;
double x,y,d,k,minx,maxx,miny,maxy;
if (fabs(x1-x2)x2?x2:x1;
miny=y1>y2?y2:y1;
maxx=x1>x2?x1:x2;
maxy=y1>y2?y1:y2;
if ((maxx-x>-minjd && x-minx>-minjd)&&(maxy-y>-minjd && y-miny>-minjd))
return d;
d=sqrt((x1 - px) * (x1 - px) + (y1 - py) * (y1 - py));
if (sqrt((x2 - px) * (x2 - px) + (y2 - py) * (y2 - py))>x1>>y1>>x2>>y2>>px>>py)
cout<建立一个从double到int的映射,从而可以处理实数。
******************************************************************************/
#include
#include
本文档为【杭州电子科技大学ACM集训队资料集】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。