C語言常用代碼

1、列的#include<iostream>using namespace std;void fullxunhuan(int *a,int n)int t=0;int m1,m2;if(n%2!=0)n+;for(int i=0;i<n%2;i+)for(m1=i,m2=n-i-1;m1<=n-i-1;m1+) am1m2=t%n+1; t+;for(-m1,-m2;m2>i;m2-) am1m2=t%n+1; t+;for(;m1>i;m1-) am1m2=t%n+1; t+; for(;m2<n-i-1;m2+) am1m2=t%n+1; t+;voi

2、d print(int *a,int n)for(int i=0;i<n;i+)for(int j=0;j<n;j+)cout<<aij<<"t"cout<<"n"void main()int *a;int n;cout<<" 請輸入 N"<<endl;cin>>n;a=new int *n;/ 申請一個 N 行 N 數(shù)組for(int i1=0;i1<n;i1+)ai1=new intn;for(int i=0;i<n;i+)/ 給數(shù)組初

3、始化for(int j=0;j<n;j+)aij=0;fullxunhuan(a,n);print(a,n);ACM小組內(nèi)部預(yù)定函數(shù)數(shù)學(xué)問題：1精度計算大數(shù)階乘2精度計算乘法（大數(shù)乘小數(shù)）3精度計算乘法（大數(shù)乘大數(shù)）4精度計算一一加法5精度計算一一減法6任意進制轉(zhuǎn)換7最大公約數(shù)、最小公倍數(shù)8組合序列9快速傅立葉變換（FFT）10. Ro nberg算法計算積分11行列式計算12.求排列組合數(shù)字符串處理：1. 字符串替換2. 字符串查找3. 字符串截取計算幾何：1. 叉乘法求任意多邊形面積2. 求三角形面積3. 兩矢量間角度4. 兩點距離（2D、3D）5射向法判斷點是否在多邊形內(nèi)部6.判斷

4、點是否在線段上7判斷兩線段是否相交8. 判斷線段與直線是否相交9. 點到線段最短距離10. 求兩直線的交點11. 判斷一個封閉圖形是凹集還是凸集12. Graham掃描法尋找凸包數(shù)論：1. x的二進制長度2. 返回x的二進制表示中從低到高的第i位3. 模取幕運算4. 求解模線性方程5. 求解模線性方程組（中國余數(shù)定理）6. 篩法素數(shù)產(chǎn)生器7. 判斷一個數(shù)是否素數(shù)圖論：1. Prim算法求最小生成樹2. Dijkstra算法求單源最短路徑3. Bellman-ford算法求單源最短路徑4. Floyd算法求每對節(jié)點間最短路徑排序/查找：1. 快速排序2. 希爾排序3. 選擇法排序4. 二分查找數(shù)

5、據(jù)結(jié)構(gòu)：1. 順序隊列2. 順序棧3. 鏈表4. 鏈棧5. 二叉樹一、數(shù)學(xué)問題1. 精度計算大數(shù)階乘語法：int result=factorial（ intn）;參數(shù)：n: n的階乘返回值：階乘結(jié)果的位數(shù)本程序直接輸出n!的結(jié)果，需要返回結(jié) 果請保留long a需要math.h源程序：int factorial( int n)long a10000;int i,j,l,c,m=0,w;a0=1;for(i=1;i<=n ;i+)c=0;for(j=0;j<=m;j+)aj=aj*i+c;c=aj/10000; aj=aj%10000;if(c>0) m+;am=c;w=m*4

6、+log10(am)+1;printf("n%ld",am);for(i=m-1;i>=0;i-) printf("%4.4ld",ai); return w;2. 精度計算乘法(大數(shù)乘小數(shù)) 語法： mult(char c,char t,int m); 參數(shù)：c：被乘數(shù)，用字符串表示，位數(shù)不限t： 結(jié)果，用字符串表示m： 乘數(shù)，限定 10 以內(nèi)返回值： null需要 string.h 源程序：void mult(char c,char t,int m)int i,l,k,flag,add=0; char s100; l=strlen(c);for

7、 (i=0;i<l;i+)sl-i-1=ci-'0'for (i=0;i<l;i+) k=si*m+add;if (k>=10) si=k%10;add=k/10;flag=1; else si=k;flag=0;add=0;if (flag) l=i+1;si=add; else l=i;for (i=0;i<l;i+) tl-1-i=si+'0'tl='0'3. 精度計算乘法(大數(shù)乘大數(shù)) 語法： mult(char a,char b,char s);參數(shù)：a： 被乘數(shù)，用字符串表示，位數(shù)不限 b： 乘數(shù)，用字符串表示

8、，位數(shù)不限 t： 結(jié)果，用字符串表示返回值： null空間復(fù)雜度為o(n A2)需要 string.h 源程序：void mult(char a,char b,char s) int i,j,k=0,alen,blen,sum=0,res6565=0,flag=0;char result65; alen=strlen(a);blen=strlen(b);for (i=0;i<alen;i+)for(j=0;j<blen;j+)resij=(ai-'0')*(bj-'0');for (i=alen-1;i>=0;i-) for(j=blen-1;

9、j>=0;j-)sum=sum+resi+blen-j-1j;resultk=sum%10; k=k+1;sum=sum/10;for (i=blen-2;i>=0;i-)for(j=0;j<=i;j+)sum=sum+resi-jj;resultk=sum%10; k=k+1;sum=sum/10;if (sum!=0) resultk=sum;k=k+1;for (i=0;i<k;i+) resulti+='0'for (i=k-1;i>=0;i-) si=resultk-1-i; sk='0'while(1)if (strle

10、n(s)!=strlen(a)&&s0='0') strcpy(s,s+1);elsebreak;4. 精度計算加法語法： add(char a,char b,char s); 參數(shù)：a： 被乘數(shù)，用字符串表示，位數(shù)不限 b：乘數(shù)，用字符串表示，位數(shù)不限t ： 結(jié)果，用字符串表示 返回值： null空間復(fù)雜度為o(n A2)需要 string.h源程序：void add(char a,char b,char back)int i,j,k,up,x,y,z,l;char *c;if (strlen(a)>strlen(b) l=strlen(a)+2; el

11、se l=strlen(b)+2;c=(char *) malloc(l*sizeof(char); i=strlen(a)-1;j=strlen(b)-1;k=0;up=0; while(i>=0|j>=0)if(i<0) x='0' else x=ai;if(j<0) y='0' else y=bj; z=x-'0'+y-'0'if(up) z+=1;if(z>9) up=1;z%=10; else up=0;ck+=z+'0'i-;j-;if(up) ck+='1'

12、;i=0;ck='0' for(k-=1;k>=0;k-) backi+=ck;backi='0'5. 精度計算減法語法： sub(char s1,char s2,char t);參數(shù)：s1：被減數(shù)， 用字符串表示， 位數(shù)不限s2：減數(shù)，用字符串表示，位數(shù)不限t ： 結(jié)果，用字符串表示返回值： null默認s1>=s2，程序未處理負數(shù)情況需要 string.h 源程序：void sub(char s1,char s2,char t) int i,l2,l1,k;l2=strlen(s2);l1=strlen(s1);tl1='0'l1

13、-;for (i=l2-1;i>=0;i-,l1-)if (s1l1-s2i>=0)tl1=s1l1-s2i+'0'else tl1=10+s1l1-s2i+'0's1l1-1=s1l1-1-1;k=l1;while(s1k<0)s1k+=10;s1k-1-=1;k-;while(l1>=0) tl1=s1l1;l1-; loop:if (t0='0')l1=strlen(s1);for (i=0;i<l1-1;i+) ti=ti+1;tl1-1='0'goto loop;if (strlen(t)=

14、0) t0='0't1='0'6. 任意進制轉(zhuǎn)換語 法 ： conversion(char s1,char s2,long d1,long d2);參數(shù)：s： 原進制數(shù)字，用字符串表示s2： 轉(zhuǎn)換結(jié)果，用字符串表示d1：原進制數(shù)d2： 需 要轉(zhuǎn)換到的進制數(shù)返回值： null高于9的位數(shù)用大寫A''Z'表示，216 位進制通過驗證 源程序：void conversion(char s,char s2,long d1,long d2)long i,j,t,num;char c;num=0;for (i=0;si!='0'i+)

15、if (si<='9'&&si>='0')t=si-'0'else t=si-'A'+10;num=num*d1+t; i=0;while(1)t=num%d2;if (t<=9)s2i=t+'0' elses2i=t+'A'-10;num/=d2;if (num=0) break;i+;參數(shù)：a：int a,求最大公約數(shù)或最小公倍數(shù)b： int b ，求最大公約數(shù)或最小公倍數(shù)返回值：返回最大公約數(shù)(hcf)或最小公倍數(shù)( lcd)lcd 需要連同 hcf 使用源程

16、序：int hcf(int a,int b)int r=0;while(b!=0) r=a%b; a=b; b=r;return(a);lcd(int u,int v,int h)return(u*v/h);8. 組合序列語法： m_of_n(int m, int n1, int m1, int* a, int head)參數(shù)：m： 組合數(shù) C 的上參數(shù)n1： 組合數(shù) C 的下參數(shù)m1：組合數(shù) C 的上參數(shù),遞歸之用*a： 1 n 的整數(shù)序列數(shù)組head：頭指針返回值：nullfor (j=0;j<i/2;j+)c=s2j;s2j=si-j;s2i-j=c; s2i+1='0&#

17、39;7. 最大公約數(shù)、最小公倍數(shù)語法： resulet=hcf(int a,int b)、result=lcd(inta,int b)*a 需要自行產(chǎn)生 初始調(diào)用時, m=m1 、 head=0 調(diào) 用 例 子 ： 求 C(m,n) 序 列m_of_n(m,n,m,a,0);源程序：void m_of_n(int m, int n1, int m1, int* a, int head)int i,t;if(m1<0 | m1>n1) return;if(m1=n1)for(i=0;i<m;i+) cout<<ai<<' ' /輸出序列

18、cout<<'n'return;m_of_n(m,n1-1,m1,a,head); / 遞歸調(diào)用t=ahead;ahead=an1-1+head;an1-1+head= t;m_of_n(m,n1-1,m1-1,a,head+1); / 再次 遞歸調(diào)用t=ahead;ahead=an1-1+head;an1-1+head= t;9. 快速傅立葉變換( FFT )語 法 ： kkfft(double pr,double pi,int n,int k,double fr,double fi,int l,int il);參數(shù)：prn：輸入的實部pin ：數(shù)入的虛部n, k

19、:滿足 n=2Akfrn ：輸出的實部fin :輸出的虛部l: 邏輯開關(guān)， 0 FFT， 1 ifFTil: 邏輯開關(guān)， 0 輸出按實部 / 虛部； 1 輸 出按模 / 幅角返回值:null需要 math.h 源程序:void kkfft(pr,pi,n,k,fr,fi,l,il)int n,k,l,il;double pr,pi,fr,fi;int it,m,is,i,j,nv,l0;double p,q,s,vr,vi,poddr,poddi;for (it=0; it<=n-1; it+)m=it; is=0;for (i=0; i<=k-1; i+)j=m/2; is=2*

20、is+(m-2*j); m=j;frit=pris; fiit=piis;pr0=1.0; pi0=0.0; p=6.283185306/(1.0*n);pr1=cos(p); pi1=-sin(p);if (l!=0) pi1=-pi1;for (i=2; i<=n-1; i+)p=pri-1*pr1;q=pii-1*pi1; s=(pri-1+pii-1)*(pr1+pi1); pri=p-q; pii=s-p-q;for (it=0; it<=n-2; it=it+2)vr=frit; vi=fiit;frit=vr+frit+1; fiit=vi+fiit+1; frit+

21、1=vr-frit+1;fiit+1=vi-fiit+1;m=n/2; nv=2;for (l0=k-2; l0>=0; l0-)m=m/2; nv=2*nv;for (it=0; it<=(m-1)*nv; it=it+nv)for (j=0; j<=(nv/2)-1; j+) p=prm*j*frit+j+nv/2; q=pim*j*fiit+j+nv/2; s=prm*j+pim*j;s=s*(frit+j+nv/2+fiit+j+nv/2);poddr=p-q; poddi=s-p-q;frit+j+nv/2=frit+j-poddr;fiit+j+nv/2=fiit

22、+j-poddi;frit+j=frit+j+poddr; fiit+j=fiit+j+poddi; if (l!=0)for (i=0; i<=n-1; i+)fri=fri/(1.0*n);fii=fii/(1.0*n); if (il!=0)for (i=0; i<=n-1; i+) pri=sqrt(fri*fri+fii*fii); if(fabs(fri)<0.000001*fabs(fii)if (fii*fri)>0) pii=90.0; else pii=-90.0; elsepii=atan(fii/fri)*360.0/6.283185306; r

23、eturn;10. Ronberg 算法計算積分語法： result=integral(double a,double b); 參數(shù)： a： 積分上限 b ： 積分下限 function f ： 積分函數(shù)返回值： f在(a,b)之間的積分值function f(x) 需要自行修改， 程序中用的 是 sina(x)/x需要 math.h 默認精度要求是 1e-5 源程序：double f(double x)return sin(x)/x; / 在這里插入被積函數(shù) double integral(double a,double b) double h=b-a;double t1=(1+f(b)*h

24、/2.0;int k=1;double r1,r2,s1,s2,c1,c2,t2;loop:double s=0.0;double x=a+h/2.0;while(x<b)s+=f(x);x+=h;t2=(t1+h*s)/2.0; s2=t2+(t2-t1)/3.0;if(k=1) k+;h/=2.0;t1=t2;s1=s2; goto loop;c2=s2+(s2-s1)/15.0;if(k=2) c1=c2;k+;h/=2.0; t1=t2;s1=s2; goto loop;r2=c2+(c2-c1)/63.0;if(k=3)r1=r2; c1=c2;k+; h/=2.0;t1=t2

25、;s1=s2;goto loop; while(fabs(1-r1/r2)>1e-5) r1=r2;c1=c2;k+; h/=2.0;t1=t2;s1=s2;goto loop;return r2;11. 行列式計算語法： result=js(int s,int n) 參數(shù)：s： 行列式存儲數(shù)組 n： 行列式維數(shù)，遞歸用 返回值： 行列式值函數(shù)中常數(shù) N 為行列式維度，需自行 定義 源程序：int js(s,n)int sN,n;int z,j,k,r,total=0;int bNN;/*bNN 用于存放，在矩陣sNN中元素s0的余子式*/if(n>2)for(z=0;z<n

26、;z+)for(j=0;j<n-1;j+) for(k=0;k<n-1;k+) if(k>=z) bjk=sj+1k+1; else bjk=sj+1k;if(z%2=0)r=s0z*js(b,n-1);/* 遞歸調(diào)用 */else r=(-1)*s0z*js(b,n-1);total=total+r;else if(n=2)total=s00*s11-s01*s10;return total;12. 求排列組合數(shù)語法： result=P(long n,long m); / result=long C(long n,long m);參數(shù)： m： 排列組合的上系數(shù) n： 排列組

27、合的下系數(shù) 返回值： 排列組合數(shù)符合數(shù)學(xué)規(guī)則：m< = n源程序：long P(long n,long m)long p=1;while(m!=0)p*=n;n-;m-;return p;long C(long n,long m)long i,c=1;i=m;while(i!=0)c*=n;n-;i-;while(m!=0) c/=m;m-;return c;二、字符串處理1. 字符串替換語法： replace(char str,char key,char swap);參數(shù)：str：在此源字符串進行替換操作key：被替換的字符串，不能為空串swap：替換的字符串，可以為空串， 為空串表示

28、在源字符中刪除 key返回值：null默認str長度小于1000,如否，重新設(shè)定設(shè)定 tmp 大小需要 string.h源程序：void replace(char str,char key,char swap)int l1,l2,l3,i,j,flag;char tmp1000;l1=strlen(str);l2=strlen(key);l3=strlen(swap);for (i=0;i<=l1-l2;i+)flag=1;for (j=0;j<l2;j+)if (stri+j!=keyj) flag=0;break;if (flag) strcpy(tmp,str); strcp

29、y(&tmpi,swap); strcpy(&tmpi+l3,&stri+l2); strcpy(str,tmp);i+=l3-1;l1=strlen(str);2. 字符串查找語法： result=strfind(char str,char key); 參數(shù)：str： 在此源字符串進行查找操作 key： 被查找的字符串，不能為空串 返回值： 如果查找成功， 返回 key 在 str 中第一次出現(xiàn)的位置，否則返回 -1需要 string.h 源程序：int strfind(char str,char key)int l1,l2,i,j,flag;l1=strlen(st

30、r);l2=strlen(key);for (i=0;i<=l1-l2;i+)flag=1;for (j=0;j<l2;j+)if (stri+j!=keyj) flag=0;break;if (flag) return i;return -1;3. 字符串截取語 法 ： mid(char str,int start,int len,char strback)參數(shù)：str ： 操作的目標(biāo)字符串start： 從第 start 個字符串開始， 截取長度 為 len 的字符len：從第 start 個字符串開始， 截取長度為 len 的字符strback： 截取的到的字符 返回值：0：超

31、出字符串長度，截取失?。?1：截取成功需要 string.h 源程序：int mid(char str,int start,int len,char strback)int l,i,k=0; l=strlen(str);if (start+len>l) return 0;for (i=start;i<start+len;i+) strbackk+=stri;strbackk='0' return 1;三、計算幾何1. 叉乘法求任意多邊形面積 語法 ： result=polygonarea(Point *polygon,int N);參數(shù)：*polygon ： 多變形

32、頂點數(shù)組 N ： 多邊形頂點數(shù)目 返回值： 多邊形面積支持任意多邊形，凹、凸皆可多邊形頂點輸入時按順時針順序排列 源程序：typedef struct double x,y; Point;double polygonarea(Point *polygon,int N)需要 math.hint i,j;double area = 0;for (i=0;i<N;i+) j = (i + 1) % N;area += polygoni.x * polygonj.y;area -= polygoni.y * polygonj.x; area /= 2;return(area < 0 ? -

33、area : area);2. 求三角形面積語 法 ： result=area3(float x1,float y1,float x2,float y2,float x3,float y3);參數(shù)：x13: 三角形3個頂點x坐標(biāo)y13: 三角形3個頂點y坐標(biāo)返回值：三角形面積需要 math.h源程序:float area3(float x1,float y1,float x2,floaty2,float x3,float y3)float a,b,c,p,s;a=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);b=sqrt(x1-x3)*(x1-x3)+(y1-y3)*

34、(y1-y3);c=sqrt(x3-x2)*(x3-x2)+(y3-y2)*(y3-y2);p=(a+b+c)/2;s=sqrt(p*(p-a)*(p-b)*(p-c);return s;3. 兩矢量間角度語 法 : result=angle(double x1, double y1, double x2, double y2);參數(shù):x/y1 2:兩矢量的坐標(biāo)返回值:兩的角度矢量返回角度為弧度制， 并且以逆時針方向 為正方向源程序:#define PI 3.1415926double angle(double x1, double y1, double x2, double y2)doubl

35、e dtheta,theta1,theta2;theta1 = atan2(y1,x1);theta2 = atan2(y2,x2);dtheta = theta2 - theta1;while (dtheta > PI)dtheta -= PI*2;while (dtheta < -PI)dtheta += PI*2;return(dtheta);4.兩點距離( 2D、3D )語法: result=distance_2d(float x1,float x2,floaty1,float y2);參數(shù):x/y/z1 2:各點的 x、y、z 坐標(biāo)返回值:兩點之間的距離注意:需要 mat

36、h.h源程序:float distance_2d(float x1,float x2,floaty1,float y2)return(sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2); float distance_3d(float x1,float x2,float y1,float y2,float z1,float z2)return(sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1 -z2)*(z1-z2);5. 射向法判斷點是否在多邊形內(nèi)部語法： result=insidepolygon(Point *polygon,int N,P

37、oint p);參數(shù)：*polygon ： 多邊形頂點數(shù)組N ： 多邊形頂點個數(shù) p： 被判斷點 返回值：0：點在多邊形內(nèi)部； 1：點在多邊形外部若 p 點在多邊形頂點或者邊上， 返回值 不確定，需另行判斷需要 math.h源程序：#define MIN(x,y) (x < y ? x : y) #define MAX(x,y) (x > y ? x : y) typedef struct double x,y; Point;int insidepolygon(Point *polygon,int N,Point p) int counter = 0;int i;double xi

38、nters;Point p1,p2;p1 = polygon0;for (i=1;i<=N;i+) p2 = polygoni % N;if (p.y > MIN(p1.y,p2.y) if (p.y <= MAX(p1.y,p2.y) if (p.x <= MAX(p1.x,p2.x) if (p1.y != p2.y) xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;if (p1.x = p2.x | p.x <= xinters)counter+;p1 = p2;if (counter % 2 = 0)re

39、turn(OUTSIDE);elsereturn(INSIDE);6. 判斷點是否在線段上語 法 ： result=Pointonline(Point p1,Point p2,Point p);參數(shù)：pl、p2 :線段的兩個端點p： 被判斷點返回值:0:點在不在線段上； 1:點在線段上若 p 線段端點上返回 1需要 math.h源程序:#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y) typedef struct double x,y; Point;int FC(double x1,double x2)

40、if (x1-x2<0.000002&&x1-x2>-0.000002) return 1; else return 0;int Pointonline(Point p1,Point p2,Point p) double x1,y1,x2,y2; x1=p.x-p1.x;x2=p2.x-p1.x; y1=p.y-p1.y;y2=p2.y-p1.y;if (FC(x1*y2-x2*y1,0)=0) return 0; if(MIN(p1.x,p2.x)<=p.x&&p.x<=MAX(p1.x,p2. x)&&(MIN(p1.

41、y,p2.y)<=p.y&&p.y<=MAX(p1.y,p2.y )return 1; else return 0;7. 判斷兩線段是否相交語 法 ： result=sectintersect(Point p1,Point p2,Point p3,Point p4);參數(shù)：pl4:兩條線段的四個端點返回值： 0：兩線段不相交； 1：兩線段 相交； 2 兩線段首尾相接p1!=p2;p3!=p4;源程序：#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct

42、 double x,y; Point;int lineintersect(Point p1,Point p2,Pointp3,Point p4)Point tp1,tp2,tp3;if(p1.x=p3.x&&p1.y=p3.y)|(p1.x=p4.x&&p1.y=p4.y)|(p2.x=p3.x&&p2.y=p3.y)|(p2.x=p4.x&&p2.y=p4.y)return 2;/ 快速排斥試驗if(MIN(p1.x,p2.x)<p3.x&&p3.x<MAX(p1.x,p2.x)&&M

43、IN(p1.y,p2.y)<p3.y<MAX(p1.y,p2.y)|(MIN(p1.x,p2.x)<p4.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p3.y<MAX(p1.y,p2.y);else return 0;/ 跨立試驗tp1.x=p1.x-p3.x;tp1.y=p1.y-p3.y;tp2.x=p4.x-p3.x;tp2.y=p4.y-p3.y;tp3.x=p2.x-p3.x;tp3.y=p2.y-p3.y;1; else return 0;8. 判斷線段與直線是否相交語 法 ： r

44、esult=lineintersect(Point p1,Point p2,Point p3,Point p4);參數(shù)：p1、p2： 線段的兩個端點p3、p4： 直線上的兩個點 返回值： 0：線段直線不相交； 1：線段 和直線相交如線段在直線上，返回 1源程序： typedef struct double x,y; Point;int lineintersect(Point p1,Point p2,Point p3,Point p4) Point tp1,tp2,tp3; tp1.x=p1.x-p3.x; tp1.y=p1.y-p3.y; tp2.x=p4.x-p3.x; tp2.y=p4.y

45、-p3.y; tp3.x=p2.x-p3.x; tp3.y=p2.y-p3.y; if1; else return 0;9. 點到線段最短距離語 法 ： result=mindistance(Point p1,Point p2,Point q);參數(shù)：p1、p2： 線段的兩個端點q： 判斷點返回值：點 q 到線段 p1p2 的距離需要 math.h源程序：#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)typedef struct double x,y; Point;double mindistance

46、(Point p1,Point p2,Point q)int flag=1;double k;Point s;if (p1.x=p2.x) s.x=p1.x;s.y=q.y;flag=0;if (p1.y=p2.y) s.x=q.x;s.y=p1.y;flag=0; if (flag) k=(p2.y-p1.y)/(p2.x-p1.x);s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1);s.y=k*(s.x-p1.x)+p1.y;if(MIN(p1.x,p2.x)<=s.x&&s.x<=MAX(p1.x,p2.x)return sqrt

47、(q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y);elsereturn MIN(sqrt(q.x-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y- p1.y),sqrt(q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y- p2.y);10. 求兩直線的交點語 法 ： result=mindistance(Point p1,Point p2,Point q);參數(shù)：plp4:直線上不相同的兩點*p： 通過指針返回結(jié)果返回值： 1 ：兩直線相交； 2：兩直線平行k1(注釋中)的值是否在01之間，用在01 之間的那個求交點源程序

48、：typedef struct double x,y; Point;int linecorss(Point p1,Point p2,Point p3,Pointp4,Point *p)double k;/ 同一直線if(p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)=0&&(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)=0) return 2;/ 平行，不同一直線if(p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)=0) return 0;

49、k=(p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)/(p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1 .y);/k1=(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)/(p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y);(*p).x=p1.x+k*(p2.x-p1.x);(*p).y=p1.y+k*(p2.y-p1.y);return 1;/ 有交點 11. 判斷一個封閉圖形是凹集還是凸集 語法： result=con

50、vex(Point *p,int n);參數(shù)：*p： 封閉曲線頂點數(shù)組n： 封閉曲線頂點個數(shù)返回值：1：凸集； -1：凹集； 0：曲線如需要判斷兩線段交點， 檢驗k和對應(yīng)默認曲線為簡單曲線：無交叉、無圈 源程序：不符合要求無法計算typedef struct double x,y; Point;int convex(Point *p,int n)int i,j,k;int flag = 0; double z;if (n < 3) return(0);for (i=0;i<n;i+) j = (i + 1) % n;k = (i + 2) % n;z = (pj.x - pi.x)

51、 * (pk.y - pj.y); z -= (pj.y - pi.y) * (pk.x - pj.x); if (z < 0)flag |= 1; else if (z > 0)flag |= 2;if (flag = 3) return 1; /CONCAVEif (flag != 0)return 1; /CONVEX else return 0;12. Graham 掃描法尋找凸包語 法 ： Graham_scan(Point PointSet,Point ch,int n,int &len);參數(shù)：PointSet： 輸入的點集ch： 輸出的凸包上的點集， 按照逆

52、時針 方向排列n： PointSet 中的點的數(shù)目 len：輸出的凸包上的點的個數(shù)返回值： null 源程序：struct Point float x,y;float multiply(Point p1,Point p2,Point p0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y- p0.y);float distance(Point p1,Point p2)return(sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)* (p1.y-p2.y);void Graham_scan(Point PointSet,

53、Point ch,int n,int &len)int i,j,k=0,top=2;Point tmp;for(i=1;i<n;i+)if(PointSeti.y<PointSetk.y)|(PointSeti.y=PointSetk.y)&&(PointSeti.x<PointSetk.x)k=i;tmp=PointSet0;PointSet0=PointSetk;PointSetk=tmp;for (i=1;i<n-1;i+)k=i;for (j=i+1;j<n;j+)if( (multiply(PointSetj,PointSetk,PointSet0)>0) |(multiply(PointSetj,PointSetk