主要加强了一下线性代数（数论应该没什么问题，就是知道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)
}
*/