主要加強了一下線性代數（數論應該沒什么問題，就是知道MR有時是不靠譜的，還有篩法的復雜度是O（nlogn））
知道N階行列式沒有多項式求法（這里還要舉行加強，比如O（n2）的求解線性方程組的方法）
然后向山大附中的同學借《組合數學》看了Polya計數法，這個比較得意，因為這個貌似比較難。
然后就是計算幾何，模板才寫了大概一半。
最新更新//2.4 加入了求平面點集的凸包的兩個算法
計算幾何模板
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
double inline max(double a,double b)
{return a>b?a:b;}
double inline min(double a,double b){return a<b?a:b;}
//計算幾何模板
//二維
//為了方便分離使用，函數盡量不調用其他函數
//基本函數：cross
const int N=100002;
const double zero=1e-8;//1e-8
const double maxnum=1e8;
const double pi=3.1415926535;
const double du=3.1415926535/180;
typedef struct {double x,y;}point;
typedef struct {point a,b;}segment;
typedef struct {double x,y;}Ds;//directed segment
typedef struct {point cl;double r;}cicle;
typedef struct {point a,b,c,d;}Rect;//
typedef struct {point a,b;}rect;//平行于坐標軸 ，左下右上
/**//*
BUG 1:輸出時有時會輸出-0.0000000 ：輸出時統一處理吧@#$%&^$#%@!#%@#!@#
*/
//*************************Point*************************//
double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
point symetrical(point a,point b){point c;c.x=b.x*2-a.x;c.y=b.y*2-a.y;return c;} //a關于b對稱
point symetrical2(point a,point b,point c); //a關于直線bc對稱
point symetrical2_fxy(point p,double a,double b,double c);//給出直線的解析式
bool online(point a,point b,point c){return (fabs(dis(a,b)+dis(a,c)-dis(b,c))<zero);}// 判定a在線段bc上
double disline(point a,point b,point c);//求點到線段的最短距離
double disline2(point a,point b,point c);//求點到直線的最短距離
double disline2_fxy(point p,double a,double b,double c){return fabs(a*p.x+b*p.y+c)/sqrt(a*a+b*b);}
//*************************Directed segment*************************//
Ds addDs(Ds a,Ds b){Ds c;c.x=a.x+b.x;c.y=a.y+b.y;return c;}
Ds rotateDs(Ds a,double A) {Ds c;c.x=a.x*cos(A)-a.y*sin(A);c.y=a.x*sin(A)+a.y*cos(A);return c;}//右旋
double dotDS(Ds a,Ds b){return a.x*b.x+a.y*b.y;}
double crossDS(Ds a,Ds b){return a.x*b.y-a.y*b.x;}
double cross(point a,point b,point c){return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}// ab ×ac
bool intersect(point a,point b,point c,point d){return((cross(a,b,c)*cross(a,b,d)<-zero)
/**//*若判斷線段和直線是否相交，則更簡單，線段跨立直線即可*/&&(cross(c,d,a)*cross(c,d,b)<-zero));}
point poi(point a, point b, point c, point d){double s1,s2;point p;s1=cross(a,b,c);s2=cross(a,b,d);
/**//*求線段的交點*/ /**//*求證明！*/ p.x=(c.x*s2-d.x*s1)/(s2-s1);p.y= (c.y*s2-d.y*s1)/(s2-s1);return p;}
//*************************Integrated skill*************************//
double area(int n,point p[N]){double s=p[n].x*p[1].y-p[1].x*p[n].y;//這里實際上是叉乘
n--;for(;n;n--)s+=p[n].x*p[n+1].y-p[n+1].x*p[n].y;return fabs(s)/2;}//
/**//**/bool inarea(point a,int n,point p[N]);//判斷點是否在多邊形內
/**//**/bool Linarea(point a,int n,point p[N]);//判斷線段是否在多邊形內 /*未開發*/ /*極難*/
cicle Outcicle(point a,point b,point c); /**//*未開發*/
cicle Incicle(point a,point b,point c); /**//*未開發*/
//********************************Convex hull******************************//
point p[N];
point q[N];
int ans[N];
bool visit[N];
int n,m,ss;
int t;
int num[N];
int a[N];
//Jarvis T=O(NM),M為凸包上的點數
void Jarvis();
void Search(int s);
bool ok(int i,int j,int k);
//Graham() T=O(NlogN)
void Graham();
void Qsort(int low,int high);
int Cross(point a,point b,point c);
void inline Change(int i,int j){point t=p[i];p[i]=p[j];p[j]=t;}
int main(){
//Jarvis();
//Graham();
}
bool inarea(point a,int n,point p[N]){
int count=false;
point t;t.x=-maxnum;t.y=a.y;//t：a左側的無窮遠處
p[n+1]=p[1];
for(int i=1;i<=n;i++) {
if(online(a,p[i],p[i+1]))
return true;
if(p[i].y==a.y&&p[i].x<a.x){//點在射線上，注意不要寫成了直線。
if(p[i].y==max(p[i].y,p[i+1].y))
count^=1;
}
else if(p[i+1].y==a.y&&p[i+1].x<a.x){
if(p[i+1].y==max(p[i].y,p[i+1].y))
count^=1;
}
else if((cross(p[i],p[i+1],a)*cross(p[i],p[i+1],t)<-zero)//線段相交
&&(cross(a,t,p[i])*cross(a,t,p[i+1])<-zero))
count^=1;
}
return count;
}
double disline(point a,point b,point c){//用解析法求垂足,再分類討論
point d;
if(c.x==b.x){//斜率為∞
if((a.y-b.y)*(a.y-c.y)<-zero)
return fabs(a.x-b.x);
else
return min(dis(a,b),dis(a,c));
}
double k=(c.y-b.y)/(c.x-b.x);
d.x=(k*k*b.x+k*(a.y-b.y )+a.x)/(k*k+1);
d.y=k*(d.x-b.x)+b.y;
if(online(d,b,c))
return dis(a,d);
else
return min(dis(a,b),dis(a,c));
}
double disline2(point a,point b,point c){//利用d=|Ax+By+C|/sqrt(A^2+B^2) 結果化簡版，不需判定斜率
double x1,y1,x2,y2,d;
x1=c.x-b.x;
y1=c.y-b.y;
x2=a.x-b.x;
y2=a.y-b.y;
return fabs(x1*y2-x2*y1)/sqrt(x1*x1+y1*y1);
}
point symetrical2(point a,point b,point c){//用解析法求垂足,再做對稱
point d,q;
if(b.x==c.x){//斜率為∞
q.x=b.x+c.x-a.x;
q.y=a.y;
return q;
}
double k=(c.y-b.y)/(c.x-b.x);
d.x=(k*k*b.x+k*(a.y-b.y )+a.x)/(k*k+1);
d.y=k*(d.x-b.x)+b.y;
q=symetrical(a,d);
return q;
}
point symetrical2_fxy(point p,double a,double b,double c){//__解析式版 結果化簡版，不需判定斜率
point q;
q.x=((b*b-a*a)*p.x-2*a*b*p.y-2*a*c)/(b*b+a*a);
q.y=((a*a-b*b)*p.y-2*a*b*p.x-2*b*c)/(b*b+a*a);
return q;
}
void Jarvis(){
freopen("graham.in","r",stdin);
freopen("graham.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&p[i].x,&p[i].y);
fclose(stdin);
m=1;
for(int j=2;j<=n;j++)
if((p[j].y<p[m].y)||(p[j].y==p[m].y&&p[j].x<p[m].x))
m=j;//找距離最近的點
memset(visit,false,sizeof(visit));
ss=1;
ans[1]=m;
Search(m);//搜索下一個在凸包上的點
printf("%d\n",ss);
for(int j=1;j<=ss;j++)
printf("%.0lf %.0lf\n",p[ans[j]].x,p[ans[j]].y);
fclose(stdout);
}
void Search(int s){
int i,j,k;
for(i=1;i<=n;i++)
if(false==visit[i]&&i!=s) //找還沒有判定的點，也不是正在判定的s
break;
k=i;
for(j=i+1;j<=n;j++)//尋找可判定的點
if(false==visit[j]&&j!=s&&ok(s,k,j))k=j;
visit[k]=true;
if(k!=m){//記錄，判定下一個
ss++;
ans[ss]=k;
Search(k);
}
}
bool ok(int i,int j,int k){
double cha=cross(p[i],p[j],p[k]);
double len1=dis(p[i],p[j]);
double len2=dis(p[i],p[k]);
if(cha<-zero)//在內部
return true;
else if(fabs(cha)<zero&&len2>len1)//在邊上選擇更遠的點
return true;
else
return false;
}
void Graham(){
freopen("graham.in","r",stdin);
freopen("graham.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf %lf",&p[i].x,&p[i].y);
num[i]=i;
}
fclose(stdin);
int ii=1;
for(int i=2;i<=n;i++)
if(p[i].y<p[ii].y||(p[i].y==p[ii].y&&p[i].x<p[ii].x))//選擇一個必定在凸包上的點
ii=i;
Change(1,ii);
Qsort(2,n);
int t=1;
a[1]=1;
a[2]=2;
a[3]=3;
t=3;
for(int i=4;i<=n;i++){//模擬棧
while(Cross(p[a[t-1]],p[a[t]],p[i]))t--;
t++;a[t]=i;
}
printf("%d\n",t);
for(int i=1;i<=t;i++)
printf("%.0lf %.0lf\n",p[a[i]].x,p[a[i]].y);
fclose(stdout);
}
int inline Cross(point a,point b,point c){
if(cross(a,b,c)<-zero||(fabs(cross(a,b,c)))<zero&&dis(a,b)<dis(a,c))
return true;
else return false;
}
void Qsort(int low,int high){
if(low==high)return;
Qsort(low,(low+high)/2);
Qsort((low+high)/2+1,high);
int a=low,b=(low+high)/2+1;
for(int i=low;i<=high;i++){
if(Cross(p[1],p[a],p[b])&&b<=high||a>(low+high)/2){
q[i]=p[b];
b++;
}
else{
q[i]=p[a];
a++;
}
}
for(int i=low;i<=high;i++)
p[i]=q[i];
}
/**//*公式
S=a*h/2 (底*高/2)
S=a*b*sinC/2 (兩邊和夾角)
S=sqrt(p*(p-a)*(p-b)*(p-c)) p=(a+b+c)/2
(已知3邊長)
S=a*b*c/(4R) (已知3邊長和外接圓半徑R)
S=(a+b+c)/(2r) (已知3邊長和內接圓半徑r)
S=|cross(A,B,C)|/2 (叉積的一半)
INcicle
半徑r=S/p=2S/(a+b+c)
圓心
對于三角形ABC,cross(A,B,C)>0
將有向線段AB逆時針旋C/2度,得到線段seg1
將有向線段CB逆時針旋A/2度,得到線段seg2
圓心就是seg1和seg2的交點
*/
/**//*三維 （未整理）
double cross(point a,point b,point c)
{ point p;
p.x = a.y*b.z-a.z*b.y;
p.y=a.z*b.x-a.x*b.z;
p.z=a.x*b.y-a.y*b.x;
return(sqrt(p.x*p.x+p.y*p.y+p.z*p.z)
}
*/