模板总结

数学知识

 

数论:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
//组合数
//C(n,m) 在n个数中选m个的方案数
ll C[N][N];
void  get_C( int  n)
{
     for ( int  i=1;i<=n;i++)
     {
         C[i][i]=C[i][0]=1;
         for ( int  j=1;j<i;j++)
             C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
     }
}
//欧几里得算法
//(a,b)
ll gcd(ll a,ll b)
{
     return  b==0? a:gcd(b,a%b);
}
//拓展欧几里得算法
//解同余方程 a*x+b*y = (a,b)
ll exgcd(ll a,ll b,ll& d,ll& x,ll& y)
{
     if (!b) { d=a; x=1; y=0; }
     else  { exgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
//逆元
//a*inv(a,n) = 1 mod n
ll inv(ll a,ll n)
{
     ll d,x,y;
     exgcd(a,n,d,x,y);
     return  d==1? (x+n)%n:-1;
}
//lucas定理
//计算较大,有模数的组合数
ll fac[N];
void  get_pre( int  n)
{
     for ( int  i=1;i<=n;i++)
         fac[i]=(fac[i-1]*i)%mod;
}
ll C(ll n,ll m,ll mod)
{
     if (n<m)  return  0;
     if (n<mod&&m<mod)
         return  fac[n]*inv(fac[m],mod)%mod*inv(fac[n-m],mod)%mod;
     return  C(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod;
}
//快速幂
//a^p % mod
ll  pow (ll a,ll p,ll mod)
{
     ll ans=1;
     while (p)
     {
         if (p&1) ans=(ans*a)%mod;
         a=(a*a)%mod; p>>=1;
     }
     return  ans;
}
//中国剩余定理
//解线性同余方程组
//sigma{ ai*(1-ai*mi) } % M  , ai*mi+wi*y=1
ll a[N],m[N];
ll china( int  n)
{
     ll M=1,d,x=0,y;
     for ( int  i=1;i<=n;i++) M*=m[i];
     for ( int  i=1;i<=n;i++)
     {
         ll w=M/m[i];
         exgcd(m[i],w,d,d,y);
         x=(x+y*w*a[i])%M;
     }
     return  (x+M)%M;
}
//大步小步算法
//计算a^x=b mod n中的最小x
map< int , int > mp;
int  BSGS( int  a, int  b, int  n)
{
     int  m= sqrt (n)+1,e=1,i;
     int  v=inv( pow (a,m,n),n);
     mp[e]=0;
     for (i=1;i<m;i++)
     {
         e=(e*m)%n;
         if (!mp.count(e)) mp[e]=i;
     }
     for (i=0;i<m;i++)
     {
         if (mp.count(b))  return  i*m+mp[b];
         b=(b*v)%mod;
     }
     return  -1;
}
//快速筛法求素数表
int  su[N],vis[N];
void  get_su( int  n)
{
     for ( int  i=2;i<=n;i++)
     {
         if (!vis[i]) su[++su[0]]=i;
         for ( int  j=1;j<=su[0]&&i*su[j]<=n;j++)
         {
             vis[i*su[j]]=1;
             if (i%su[j]==0)  break ;
         }
     }
}
//欧拉函数
//phi(n)小于n的数中与n互素的数的个数
ll get_phi( int  n)
{
     int  m= sqrt (n)+1;
     ll ans=n;
     for ( int  i=2;i<=m;i++)  if (n%i==0)
     {
         ans=ans/i*(i-1);
         while (n%i==0) n/=i;
     }
     if (n>1) ans=ans/n*(n-1);
     return  ans;
}
ll phi[N];
void  get_phi_table( int  n)
{
     phi[1]=1;
     for ( int  i=2;i<=n;i++)  if (!phi[i])
     {
         for ( int  j=i;j<=n;j+=i)
         {
             if (!phi[j]) phi[j]=j;
             phi[j]=phi[j]/i*(i-1);
         }
     }
}<br> //莫比乌斯函数
int  mu[N],su[N],vis[N];
void  get_mu( int  n)
{
     mu[1]=1;
     for ( int  i=2;i<=n;i++)
     {
         if (!vis[i]) mu[i]=-1,su[++su[0]]=i;
         for ( int  j=1;j<=su[0]&&i*su[j]<=n;j++)
         {
             vis[i*su[j]]=1;
             if (i%su[j]==0) mu[i*su[j]]=0;
             else  mu[i*su[j]]=-mu[i];
         }
     }
}
//高斯消元
//解线性方程组
double  a[N][N];
void  gause( int  n)
{
     for ( int  i=1;i<=n;i++)
     {
         int  r=i;
         for ( int  j=i+1;j<=n;j++)
             if ( fabs (a[j][i])> fabs (a[r][i])) r=i;
         for ( int  j=1;j<=n+1;j++) swap(a[i][j],a[r][j]);
         for ( int  j=n+1;j>=i;j--)
             for ( int  k=i+1;k<=n;k++)
                 a[k][j]-=a[k][i]/a[i][i]*a[i][j];
     }
     for ( int  i=n;i;i--)
     {
         for ( int  j=i+1;j<=n;j++)
             a[i][n+1]-=a[j][n+1]*a[i][j];
         a[i][n+1]/=a[i][i];
     }
}

 

高精度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
int  trans( char * s, int  st, int  ed)
{
     int  x=0;
     for ( int  i=st;i<ed;i++) x=x*10+s[i]- '0' ;
     return  x;
}
 
struct  Bign
{
     int  len; ll N[maxn];
     Bign() { len=0;  memset (N,0, sizeof (N)); }
     Bign(ll num) {  * this =num; }
     Bign( const  char * s) { * this =s; }
     void  print()
     {
         printf ( "%d" ,N[len-1]);
         for ( int  i=len-2;i>=0;i--)
             printf ( "%08d" ,N[i]);
         puts ( "" );
     }
     Bign operator = ( const  ll x)
     {
         ll num=x;
         while (num>base)
         {
             N[len++]=num%base;
             num/=base;
         }
         if (num) N[len++]=num;
         return  * this ;
     }
     Bign operator = ( char * s)
     {
         int  L= strlen (s);
         len=(L-1)/wlen+1;
         for ( int  i=0;i<len;i++)
         {
             int  ed=L-i*wlen;
             int  st=max(0,ed-wlen);
             N[i]=trans(s,st,ed);
         }
         return  * this ;
     }
     bool  operator < ( const  Bign& B)  const
     {
         if (len!=B.len)  return  len<B.len;
         for ( int  i=len-1;i>=0;i--)
             if (N[i]!=B.N[i])  return  N[i]<B.N[i];
         return  0;
     }
     bool  operator <= ( const  Bign& B)  const
     {
         return  !(B<(* this ));
     }
      
     void  clear()
     {
         while (len>1&&N[len-1]==0) len--;
     }
      
     Bign operator + ( const  Bign& B)  const
     {
         Bign C;
         C.len=max(len,B.len)+10;
         for ( int  i=0;i<C.len;i++)
         {
             C.N[i]+=N[i]+B.N[i];
             C.N[i+1]+=C.N[i]/base;
             C.N[i]%=base;
         }
         C.clear();
         return  C;
     }
     Bign operator - (Bign B)
     {
         Bign C=* this ;
         C.len=max(C.len,B.len);
         for ( int  i=0;i<C.len;i++)
         {
             if (C.N[i]<B.N[i]) C.N[i+1]--,C.N[i]+=base;
             C.N[i]=C.N[i]-B.N[i];
         }
         C.clear();
         return  C;
     }
     Bign operator * ( const  Bign& B)  const
     {
         Bign C;
         C.len=len+B.len;
         for ( int  i=0;i<len;i++)
             for ( int  j=0;j<B.len;j++)
                 C.N[i+j]+=N[i]*B.N[j];
         for ( int  i=0;i<C.len;i++)
         {
             C.N[i+1]+=C.N[i]/base;
             C.N[i]%=base;
         }
         C.clear();
         return  C;
     }
     Bign operator / ( const  Bign& B)
     {
         Bign C,F;
         C.len=len;
         for ( int  i=len-1;i>=0;i--)
         {
             F=F*base;
             F.N[0]=N[i];
             while (B<=F)
             {
                 F=F-B;
                 C.N[i]++;
             }
         }
         C.clear();
         return  C;
     }
     Bign operator % ( const  Bign& B)
     {
         Bign r=* this /B;
         return  * this -r*B;
     }
  
}A,B;

  

 

矩阵乘法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//矩阵乘法
struct  Mat
{
     int  r,c; ll N[maxn][maxn];
     Mat( int  r=0, int  c=0)
     {
         this ->r=r, this ->c=c;
         memset (N,0, sizeof (N));
     }
     Mat operator * ( const  Mat& B)  const
     {
         Mat C(r,B.c);
         for ( int  i=0;i<r;i++)
             for ( int  j=0;j<B.c;j++)
                 for ( int  k=0;k<c;k++)
                     C.N[i][j]=(C.N[i][j]+N[i][k]*B.N[k][j])%mod;
         return  C;
     }
     Mat operator ^ ( int  p)
     {
         Mat ans(r,r),tmp=* this ;
         for ( int  i=0;i<r;i++) ans.N[i][i]=1;
         while (p)
         {
             if (p&1) ans=ans*tmp;
             tmp=tmp*tmp; p>>=1;
         }
         return  ans;
     }
     
};

 

 

数据结构

 

树状数组:

1
2
3
4
5
6
7
8
9
10
11
12
//树状数组
int  C[N],mx;
void  Add( int  x, int  v)
{
     for ( int  i=x;i<=mx;i+=i&-i) C[i]+=v;
}
int  query( int  x)
{
     int  ans=0;
     for ( int  i=x;i;i-=i&-i) ans+=C[i];
     return  ans;
}

  

线段树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//线段树
//区间加,区间乘,区间求和
int  mod;
struct  Tnode
{
     int  u,l,r;
     ll sum,add,mul;
     void  mulv(ll x) {
         sum=(sum*x)%mod;
         mul=(mul*x)%mod;
         add=(add*x)%mod;
     }
     void  addv(ll x) {
         sum=(sum+(r-l+1)*x%mod)%mod;
         add=(add+x)%mod;
     }
     void  pushdown() ;
     void  maintain() ;
}T[N];
void  Tnode::pushdown() {
     if (mul^1) {
         T[u<<1].mulv(mul);
         T[u<<1|1].mulv(mul);
         mul=1;
     }
     if (add) {
         T[u<<1].addv(add);
         T[u<<1|1].addv(add);
         add=0;
     }
}
void  Tnode::maintain() {
     sum=(T[u<<1].sum+T[u<<1|1].sum)%mod;
}
 
void  update( int  u, int  L, int  R, int  x, int  f)
{
     T[u].pushdown();
     if (L<=T[u].l&&T[u].r<=R) {
         if (!f) T[u].addv(x);
         else  T[u].mulv(x);
     else  {
         int  mid=T[u].l+T[u].r>>1;
         if (L<=mid) update(u<<1,L,R,x,f);
         if (mid<R) update(u<<1|1,L,R,x,f);
         T[u].maintain();
     }
}
ll query( int  u, int  L, int  R)
{
     T[u].pushdown();
     if (L<=T[u].l&&T[u].r<=R)
         return  T[u].sum;
     else  {
         int  mid=T[u].l+T[u].r>>1;
         ll ans=0;
         if (L<=mid) ans=(ans+query(u<<1,L,R))%mod;
         if (mid<R) ans=(ans+query(u<<1|1,L,R))%mod;
         return  ans;
     }
}
ll a[N];
 
void  build( int  u, int  l, int  r)
{
     T[u]=(Tnode){ u,l,r,0,0,1 };
     if (l==r) {
         T[u].sum=a[l];
     else  {
         int  mid=l+r>>1;
         build(u<<1,l,mid);
         build(u<<1|1,mid+1,r);
         T[u].maintain();
     }
}

 

Treap:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//Treap
struct  Node
{
     Node *ch[2];
     int  v,r,m,w,s;
     Node( int  v):v(v) { ch[0]=ch[1]=NULL; r= rand (); s=w=1; }
     int  cmp( int  x) {
         if (v==x)  return  -1;
         return  x<v? 0:1;
     }
     void  maintain() {
         s=w;
         if (ch[0]!=NULL) s+=ch[0]->s;
         if (ch[1]!=NULL) s+=ch[1]->s;
     }
};
 
void  rotate(Node* &o, int  d)
{
     Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
     o->maintain(); k->maintain(); o=k;
}
void  insert(Node *&o, int  x)
{
     if (o==NULL) o= new  Node(x);
     int  d=o->cmp(x);
     if (d==-1) o->w++;
     else  {
         insert(o->ch[d],x);
         if (o->ch[d]->r > o->r) rotate(o,d^1);
     }
     o->maintain();
}
void  remove (Node *&o, int  x)
{
     int  d=o->cmp(x);
     if (d==-1)
     {
         if (o->s>1) { o->w--; o->maintain();  return  ; }
         else  {
             if (o->ch[0]!=NULL&&o->ch[1]!=NULL) {
                 int  d2=o->ch[0]->r > o->ch[1]->r ? 1:0;
                 rotate(o,d2);  remove (o->ch[d2],x);
             else  {
                 if (o->ch[0]!=NULL) o=o->ch[0];  else  o=o->ch[1];
                 delete  o;
             }
         }
     else
         remove (o->ch[d],x);
     if (o!=NULL) o->maintain();
}
int  kth(Node* o, int  rk)
{
     if (o==NULL)  return  0;
     int  s=o->ch[0]==NULL? 0:o->ch[0]->s;
     if (rk==s+1)  return  o->v;
     else  if (rk<=s)  return  kth(o->ch[0],rk);
     else  return  kth(o->ch[1],rk-s-o->w);
}
int  rank(Node* o, int  x)
{
     if (o==NULL)  return  0;
     int  s=o->ch[0]==NULL? 0:o->ch[0]->s;
     int  d=o->cmp(x);
     if (d==-1)  return  1;
     else  if (d==0)  return  rank(o->ch[0],x);
     else  return  s+o->w+rank(o->ch[1],x);
}
int  tmp;
void  before(Node* o, int  x)
{
     if (o==NULL)  return  ;
     if (o->v<x) { tmp=max(tmp,o->v); before(o->ch[1],x); }
     else  before(o->ch[0],x);
}
void  after(Node* o, int  x)
{
     if (o==NULL)  return  ;
     if (o->v>x) { tmp=min(tmp,o->v); after(o->ch[0],x); }
     else  after(o->ch[1],x);
}

 

splay:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//splay自上而下
struct  Node
{
     Node *ch[2];
     int  s;
     int  cmp( int  x)
     {
         int  d=x-ch[0]->s;
         if (d==1)  return  -1;
         return  d<=0? 0:1;
     }
     void  maintain()
     {
         s=ch[0]->s+ch[1]->s;
     }
     void  pushdown() {}
}mempool[N],*G=mempool;
 
Node* null= new  Node();
void  rotate(Node* &o, int  d)
{
     Node* k=o->ch[d^1]; o->ch[d^1]=k->ch[d],k->ch[d]=o;
     o->maintain(); k->maintain(); o=k;
}
void  splay(Node* &o, int  k)
{
     o->pushdown();
     int  d=o->cmp(k);
     if (d==1) k-=o->ch[0]->s+1;
     if (d!=-1) {
         Node* p=o->ch[d];
         p->pushdown();
         int  d2=p->cmp(k),k2=d2==0? k:k-p->ch[d]->s-1;
         if (d2!=-1) {
             splay(p->ch[d2],k2);
             if (d==d2) rotate(o,d^1);  else  rotate(o->ch[d],d);
         }
         rotate(o,d^1);
     }
}
Node* merge(Node* left,Node* right)
{
     splay(left,left->s);
     left->ch[1]=right,left->maintain();
     return  left;
}
void  split(Node* o, int  k,Node*&left,Node*&right)
{
     splay(o,k);
     left=o,right=left->ch[1],left->ch[1]=NULL;
     left->maintain();
}
Node* build( int  l, int  r)
{
     if (r<l)  return  null;
     int  mid=l+r>>1;
     G->s=1;
     G->ch[0]=build(l,mid-1);
     G->ch[1]=build(mid+1,r);
     G->maintain();
     return  G++;
}

 

主席树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//主席树
struct  Tnode
{
     Tnode *ls,*rs;
     int  sum;
} *T[N*50],mempool[N*50],*G=mempool;
 
Tnode* Nw(Tnode* l,Tnode* r, int  x)
{
     G->ls=l,G->rs=r,G->sum=x;
     return  G++;
}
Tnode* build(Tnode* p, int  l, int  r, int  pos)
{
     if (l==r)
         return  Nw(T[0],T[0],p->sum+1);
     else  {
         int  mid=l+r>>1;
         if (pos<=mid)  return  Nw(build(p->ls,l,mid,pos),p->rs,p->sum+1);
         else  return  Nw(p->ls,build(p->rs,mid+1,r,pos),p->sum+1);
     }
}
int  query(Tnode* x, int  l, int  r, int  pos)
{
     if (l==r)  return  x->sum;
     else  {
         int  mid=l+r>>1;
         if (pos<=mid)  return  query(x->ls,l,mid,pos);
         else  return  query(x->rs,mid+1,r,pos);
     }
}

 

Link-Cut-Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//Link-Cut-Tree
namespace  LCT
{
 
     struct  Node {
         Node *ch[2],*fa;
         int  rev;
         //others v
         Node() {};
         Node( int  x) ;
         void  reverse() {
             swap(ch[0],ch[1]);
             rev^=1;
         }
         void  up_push() {
             if (fa->ch[0]== this ||fa->ch[1]== this )
                 fa->up_push();
             if (rev) {
                 ch[0]->reverse();
                 ch[1]->reverse();
                 rev=0;
             }
         }
         void  maintain() { }
     } T[N<<1],*null=&T[0];
     Node::Node( int  x) {
         ch[0]=ch[1]=fa=null;
         rev=0;  //v=x;
     }
     void  rot(Node* o, int  d) {
         Node* p=o->fa;
         p->ch[d]=o->ch[d^1];
         o->ch[d^1]->fa=p;
         o->ch[d^1]=p;
         o->fa=p->fa;
         if (p==p->fa->ch[0])
             p->fa->ch[0]=o;
         else  if (p==p->fa->ch[1])
             p->fa->ch[1]=o;
         p->fa=o;
         p->maintain();
     }
     void  splay(Node* o) {
         o->up_push();
         Node *nf,*nff;
         while (o->fa->ch[0]==o||o->fa->ch[1]==o) {
             nf=o->fa,nff=nf->fa;
             if (o==nf->ch[0]) {
                 if (nf==nff->ch[0]) rot(nf,0);
                 rot(o,0);
             else  {
                 if (nf==nff->ch[1]) rot(nf,1);
                 rot(o,1);
             }
         }
         o->maintain();
     }
     void  Access(Node* o) {
         Node *son=null;
         while (o!=null) {
             splay(o);
             o->ch[1]=son;
             o->maintain();
             son=o; o=o->fa;
         }
     }
     void  evert(Node* o) {
         Access(o);
         splay(o);
         o->reverse();
     }
     void  Link(Node* u,Node* v) {
         evert(u);
         u->fa=v;
     }
     void  Cut(Node* u,Node* v) {
         evert(u);
         Access(v),splay(v);
         v->ch[0]=u->fa=null;
         v->maintain();
     }
     Node* find(Node* o) {
         while (o->fa!=null) o=o->fa;
         return  o;
     }
 
}
using  namespace  LCT ;

 

 

 

2-SAT:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//2-sat
struct  TwoSAT {
     int  n;
     vector< int > g[N<<1];
     int  st[N<<1],mark[N<<1],top;
     
     bool  dfs( int  x) {
         if (mark[x^1])  return  0;
         if (mark[x])  return  1;
         mark[x]=1;
         st[++top]=x;
         for ( int  i=0;i<g[x].size();i++)
             if (!dfs(g[x][i]))  return  0;
         return  1;
     }
     void  init( int  n) {
         this ->n=n;
         for ( int  i=0;i<2*n;i++) g[i].clear();
         memset (mark,0, sizeof (mark));
     }
     void  addc( int  x, int  xval, int  y, int  yval) {
         x=x*2+xval;
         y=y*2+yval;
         g[x^1].push_back(y);
         g[y^1].push_back(x);
     }
     bool  solve() {
         for ( int  i=0;i<2*n;i+=2) {
             if (!mark[i]&&!mark[i+1]) {
                 top=0;
                 if (!dfs(i)) {
                     while (top) mark[st[top--]]=0;
                     if (!dfs(i+1))  return  0;
                 }
             }
         }
         return  1;
     }
     
} s;

  

有向图的强联通分量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//tarjan求SCC
struct  Edge {
     int  v,nxt;
}e[M];
int  en=1,front[N];
void  adde( int  u, int  v)
{
     e[++en]=(Edge){v,front[u]}; front[u]=en;
}
 
int  n,top,dfn;
int  st[N],sccno[N],scc_cnt,pre[N],lowlink[N];
 
void  tarjan( int  u)
{
     pre[u]=lowlink[u]=++dfn;
     st[++top]=u;
     trav(u,i) {
         int  v=e[i].v;
         if (!pre[v]) {
             tarjan(v);
             lowlink[u]=min(lowlink[u],lowlink[v]);
         else
         if (!sccno[v])
             lowlink[u]=min(lowlink[u],pre[v]);
     }
     if (lowlink[u]==pre[u]) {
         scc_cnt++;
         for (;;) {
             int  x=st[top--];
             sccno[x]=scc_cnt;
             if (x==u)  break ;
         }
     }
}

 

无向图的边的双连通分量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//BCC
struct  Edge {
     int  u,v,nxt;
}e[M];
int  en=1,front[N];
void  adde( int  u, int  v)
{
     e[++en]=(Edge){u,v,front[u]}; front[u]=en;
}
 
Edge st[N];
vector< int > bcc[N];
int  pre[N],iscut[N],bccno[N],top,dfn,bcc_cnt;
 
int  dfs( int  u, int  fa)
{
     int  lowu=pre[u]=++dfn;
     int  child=0;
     trav(u,i) {
         int  v=e[i].v;
         Edge E=e[i];
         if (!pre[v]) {
             st[++top]=E;
             child++;
             int  lowv=dfs(v,u);
             lowu=min(lowu,lowv);
             if (lowv>=pre[u]) {
                 iscut[u]=1;
                 bcc_cnt++;
                 for (;;) {
                     Edge x=st[top--];
                     if (bccno[x.u]!=bcc_cnt) {
                         bccno[x.u]=bcc_cnt;
                         bcc[bcc_cnt].push_back(x.u);
                     }
                     if (bccno[x.v]!=bcc_cnt) {
                         bccno[x.v]=bcc_cnt;
                         bcc[bcc_cnt].push_back(x.v);
                     }
                     if (x.u==u&&x.v==v)  break ;
                 }
             }
         else
         if (pre[v]<pre[u] && v!=fa) {
             st[++top]=E;
             lowu=min(lowu,pre[v]);
         }
     }
     if (fa<0&&child==1) iscut[u]=0;
     return  lowu;
}

  

最短路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//spfa
 
struct  Edge {
     int  v,w,nxt;
}e[M];
int  en=1,front[N];
void  adde( int  u, int  v, int  w)
{
     e[++en]=(Edge){v,w,front[u]}; front[u]=en;
}
 
queue< int > q;
int  inq[N],dis[N];
void  spfa( int  s)
{
     dis[s]=0; inq[s]=1;
     q.push(s);
     while (!q.empty()) {
         int  u=q.front(); q.pop();
         inq[u]=0;
         trav(u,i) {
             int  v=e[i].v;
             if (dis[v]>dis[u]+e[i].w) {
                 dis[v]=dis[u]+e[i].w;
                 if (!inq[v]) {
                     inq[v]=1;
                     q.push(v);
                 }
             }
         }
     }
}
 
//dijkstra
 
struct  Node {
     int  id,dis;
     bool  operator < ( const  Node& rhs)  const
     {
         return  dis>rhs.dis;
     }
};
 
priority_queue<Node> q;
int  n,m,s;
int  vis[N],dis[N];
 
void  dijkstra( int  s)
{
     FOR(i,1,n) dis[i]=inf;
     dis[s]=0; q.push((Node){s,0});
     while (!q.empty()) {
         int  u=q.top().id;
         q.pop();
         if (vis[u])  continue ;
         vis[u]=1;
         trav(u,i) {
             int  v=e[i].v;
             if (dis[v]>dis[u]+e[i].w) {
                 dis[v]=dis[u]+e[i].w;
                 q.push((Node){v,dis[v]});
             }
         }
     }
}

  

  

最小生成树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//Kruskal
 
int  fa[N];
int  find( int  u)
{
     if (!fa[u] || u==fa[u])  return  fa[u]=u;
     return  fa[u]=find(fa[u]);
}
 
struct  Edge {
     int  u,v,w;
     bool  operator < ( const  Edge& rhs)  const
     {
         return  w<rhs.w;
     }
}e[M];
int  tot;
 
void  Kruskal()
{
     sort(e+1,e+tot+1);
     for ( int  i=1;i<=tot;i++) {
         int  u=e[i].u,v=e[i].v;
         int  x=find(u),y=find(v);
         if (x!=y) {
             fa[x]=y;
             //加入树边(u,v)
         }
     }
}

  

最大流:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//Dinic算法求最大流
struct  Edge {
     int  u,v,cap,flow;
};
struct  Dinic {
     int  d[N],cur[N],vis[N];
     vector<Edge> es;
     vector< int > g[N];
     queue< int > q;
     
     void  AddEdge ( int  u, int  v, int  w) {
         es.push_back((Edge){u,v,w,0});
         es.push_back((Edge){v,u,0,0});
         int  m=es.size();
         g[u].push_back(m-2);
         g[v].push_back(m-1);
     }
     bool  bfs( int  s, int  t) {
         memset (vis,0, sizeof (vis));
         d[s]=0; vis[s]=1;
         q.push(s);
         while (!q.empty()) {
             int  u=q.front(); q.pop();
             FOR(i,0,( int )g[u].size()-1) {
                 Edge& e=es[g[u][i]];
                 int  v=e.v;
                 if (e.cap>e.flow&&!vis[v]) {
                     vis[v]=1;
                     d[v]=d[u]+1;
                     q.push(v);
                 }
             }
         }
         return  vis[t];
     }
     int  dfs( int  u, int  a, int  t) {
         if (u==t||a==0)  return  a;
         int  flow=0,f;
         for ( int & i=cur[u];i<g[u].size();i++) {
             Edge& e=es[g[u][i]];
             int  v=e.v;
             if (d[v]==d[u]+1&&(f=dfs(v,min(a,e.cap-e.flow),t))>0) {
                 e.flow+=f;
                 es[g[u][i]^1].flow-=f;
                 flow+=f,a-=f;
                 if (!a)  break ;
             }
         }
         return  flow;
     }
     int  maxflow( int  s, int  t) {
         int  flow=0;
         while (bfs(s,t)) {
             memset (cur,0, sizeof (cur));
             flow+=dfs(s,inf,t);
         }
         return  flow;
     }
} dc;

  

最小费用最大流:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/最短路算法求最小费用最大流
struct  Edge {
     int  u,v,cap,flow,cost;
     Edge( int  _, int  __, int  ___, int  ____, int  _____)
     { u=_,v=__,cap=___,flow=____,cost=_____; }
};
 
struct  MCMF {
     int  n,m,s,t;
     int  d[N],p[N],a[N],inq[N];
     vector<Edge> es;
     vector< int > g[N];
     queue< int > q;
     void  init( int  n) {
         this ->n=n;
         es.clear();
         for ( int  i=0;i<=n;i++) g[i].clear();
     }
     void  AddEdge( int  u, int  v, int  w, int  c) {
         es.push_back(Edge(u,v,w,0,c));
         es.push_back(Edge(v,u,0,0,-c));
         int  m=es.size();
         g[u].push_back(m-2);
         g[v].push_back(m-1);
     }
     bool  spfa( int  s, int  t,ll& flow,ll& cost) {
         memset (inq,0, sizeof (inq));
         for ( int  i=0;i<=n;i++) d[i]=inf;
         inq[s]=1; d[s]=p[s]=0; a[s]=inf;
         q.push(s);
         while (!q.empty()) {
             int  u=q.front(); q.pop();
             inq[u]=0;
             for ( int  i=0;i<g[u].size();i++) {
                 Edge& e=es[g[u][i]];
                 int  v=e.v;
                 if (d[v]>d[u]+e.cost && e.cap>e.flow) {
                     d[v]=d[u]+e.cost;
                     a[v]=min(a[u],e.cap-e.flow);
                     p[v]=g[u][i];
                     if (!inq[v])
                         inq[v]=1 , q.push(v);
                 }
             }
         }
         if (d[t]==inf)  return  0;
         flow+=a[t],cost+=a[t]*d[t];
         for ( int  x=t;x!=s;x=es[p[x]].u) {
             es[p[x]].flow+=a[t];
             es[p[x]^1].flow-=a[t];
         }
         return  1;
     }
     void  mcmf( int  s, int  t,ll& cost,ll& flow) {
         flow=cost=0;
         while (spfa(s,t,cost,flow)) ;
     }
} mc;

 

KM算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//KM算法求二分图的最佳完美匹配
struct  KM {
     int  slack[N],res[N];
     int  l[N],r[N],lx[N],rx[N],g[N][N];
     
     void  clear( int  n) {
         for ( int  i=1;i<=n;i++) {
             res[i]=0;
             for ( int  j=1;j<=n;j++) g[i][j]=-1;
         }
     }
     bool  find( int  x, int  n) {
         lx[x]=1;
         for ( int  i=1;i<=n;i++)
             if (!rx[i]&&g[x][i]!=-1) {
                 int  tmp=g[x][i]-l[x]-r[i];
                 if (!tmp) {
                     rx[i]=1;
                     if (!res[i]||find(res[i],n)) {
                         res[i]=x;
                         return  1;
                     }
                 else
                     slack[i]=min(slack[i],tmp);
             }
         return  0;
     }
     int  solve( int  n) {
         if (!n)  return  0;
         for ( int  i=1;i<=n;i++) r[i]=0;
         for ( int  i=1;i<=n;i++) {
             l[i]=INF;
             for ( int  j=1;j<=n;j++)  if (g[i][j]!=-1)
                 l[i]=min(l[i],g[i][j]);
         }
         for ( int  i=1;i<=n;i++) {
             for ( int  j=1;j<=n;j++) slack[j]=INF;
             for (;;) {
                 for ( int  j=1;j<=n;j++) lx[j]=rx[j]=0;
                 if (find(i,n))  break ;
                 int  mini=INF;
                 for ( int  i=1;i<=n;i++)  if (!rx[i])
                     mini=min(mini,slack[i]);
                 for ( int  i=1;i<=n;i++) {
                     if (lx[i]) l[i]+=mini;
                     if (rx[i]) r[i]-=mini;
                     else  slack[i]-=mini;
                 }
             }
         }
         int  ans=0;
         for ( int  i=1;i<=n;i++)
             ans+=l[i]+r[i];
         return  ans;
     }
} km;

  

 

 

LCA:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//倍增法求LCA
//倍增法可以在线构造 比较灵活
struct  Edge {
     int  v,nxt;
}e[M];
int  en=1,front[N];
void  adde( int  u, int  v)
{
     e[++en]=(Edge){v,front[u]}; front[u]=en;
}
 
int  fa[N][D],dep[N];
 
void  dfs( int  u)
{
     for ( int  i=1;i<D;i++)
         fa[u][i]=fa[fa[u][i-1]][i-1];
     trav(u,i) {
         int  v=e[i].v;
         if (v!=fa[u][0]) {
             fa[v][0]=u;
             dep[v]=dep[u]+1;
             dfs(v);
         }
     }
}
int  lca( int  u, int  v)
{
     if (dep[u]<dep[v]) swap(u,v);
     int  t=dep[u]-dep[v];
     for ( int  i=0;i<D;i++)
         if (t&(1<<i)) u=fa[u][i];
     if (u==v)  return  u;
     for ( int  i=D-1;i>=0;i--)
         if (fa[u][i]!=fa[v][i])
             u=fa[u][i],v=fa[v][i];
     return  fa[u][0];
}
 
//树链剖分求LCA
//比较快
struct  Edge {
     int  v,nxt;
}e[M];
int  en=1,front[N];
void  adde( int  u, int  v)
{
     e[++en]=(Edge){v,front[u]}; front[u]=en;
}
 
int  fa[N],top[N],siz[N],dep[N],son[N];
void  dfs1( int  u)
{
     siz[u]=1; son[u]=0;
     trav(u,i) {
         int  v=e[i].v;
         if (v!=fa[u]) {
             fa[v]=u;
             dep[v]=dep[u]+1;
             dfs1(v);
             siz[u]+=siz[v];
             if (siz[v]>siz[son[u]]) son[u]=v;
         }
     }
}
void  dfs2( int  u, int  tp)
{
     top[u]=tp;
     if (son[u]) dfs2(son[u],tp);
     trav(u,i)
         if (e[i].v!=fa[u]&&e[i].v!=son[u])
             dfs2(e[i].v,e[i].v);
}
int  lca( int  u, int  v)
{
     while (top[u]!=top[v]) {
         if (dep[top[u]]<dep[top[v]]) swap(u,v);
         u=fa[top[u]];
     }
     return  dep[u]<dep[v]? u:v;
}

  

树链剖分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//树链剖分
struct  Edge {
     int  v,nxt;
}e[M];
int  en=1,front[N];
void  adde( int  u, int  v)
{
     e[++en]=(Edge){v,front[u]}; front[u]=en;
}
 
int  fa[N],top[N],siz[N],dep[N],son[N],bl[N],dfn;
void  dfs1( int  u)
{
     siz[u]=1; son[u]=0;
     trav(u,i) {
         int  v=e[i].v;
         if (v!=fa[u]) {
             fa[v]=u;
             dep[v]=dep[u]+1;
             dfs1(v);
             siz[u]+=siz[v];
             if (siz[v]>siz[son[u]]) son[u]=v;
         }
     }
}
void  dfs2( int  u, int  tp)
{
     top[u]=tp; bl[u]=++dfn;
     if (son[u]) dfs2(son[u],tp);
     trav(u,i)
         if (e[i].v!=fa[u]&&e[i].v!=son[u])
             dfs2(e[i].v,e[i].v);
}
//以合适的数据结构T维护重链
int  ans;
int  query( int  u, int  v)
{
     while (top[u]!=top[v]) {
         if (dep[top[u]]<dep[top[v]]) swap(u,v);
         ans<-query(T,bl[top[u]],bl[u]);
         u=fa[top[u]];
     }
     if (u==v)  return  ;
     if (dep[u]>dep[v]) swap(u,v);
     ans<-query(T,bl[u],bl[v]);
     <-ans
}
//类似-查询树上任意两节点的方法
void  modify() {}

  

点分治:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//点分治
struct  Edge {
     int  v,nxt;
}e[M];
int  en=1,front[N];
void  adde( int  u, int  v)
{
     e[++en]=(Edge){v,front[u]}; front[u]=en;
}
 
int  rt,n,size,vis[N],siz[N],f[N],dep[N];
 
void  get_root( int  u, int  fa)
{
     siz[u]=1; f[u]=0;
     trav(u,i) {
         int  v=e[i].v;
         if (v!=fa) {
             get_root(v,u);
             siz[u]+=siz[v];
             if (siz[v]>f[u]) f[u]=siz[v];
         }
     }
     f[u]=max(f[u],size-siz[u]);
     if (f[u]<f[rt]) rt=u;
}
void  solve( int  u)
{
     vis[u]=1;
     //计算经过根u的信息
     trav(u,i)  if (!vis[e[i].v])
     {
         //统计当前子树信息
         //与前i-1个子树信息结合计算贡献
         //将当前子树信息加入前i-1个子树信息
     }
     trav(u,i)  if (!vis[e[i].v]) {
         int  v=e[i].v;
         size=siz[v]; rt=0;
         get_root(v,-1);
         solve(rt);
     }
}
int  main()
{
     //blabla
     size=f[0]=n;
     rt=0; get_root(rt,-1);
     solve(rt);
}

  

 

字符串

 

KMP:

1
2
3
4
5
6
7
8
9
10
11
12
//KMP算法
int  f[N];  char  s[N];
void  get_fail()
{
     int  j=0;
     int  n= strlen (s+1);
     for ( int  i=2;i<=n;i++) {
         while (j&&s[j+1]!=s[i]) j=f[j];
         if (s[j+1]==s[i]) j++;
         f[i]=j;
     }
}

  

AC自动机:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//AC自动机
struct  AC_auto {
     int  sz,ch[N][26],f[N],val[N];
     AC_auto() {
         sz=1;
         memset (ch,0, sizeof (ch));
     }
     void  insert( char * s) {
         int  u=0;
         for ( int  i=0;s[i];i++) {
             int  c=s[i]- 'a' ;
             if (!ch[u][c]) ch[u][c]=++sz;
             u=ch[u][c];
         }
         val[u]=1;
     }
     void  get_fail() {
         queue< int > q;
         f[0]=0;
         for ( int  c=0;c<26;c++)
             if (ch[0][c]) f[ch[0][c]]=0,q.push(ch[0][c]);
         while (!q.empty()) {
             int  qr=q.front(); q.pop();
             for ( int  c=0;c<26;c++) {
                 int  u=ch[qr][c];
                 if (!u)  continue ;
                 q.push(u);
                 int  v=f[qr];
                 while (v&&!ch[v][c]) v=f[v];
                 if (val[ch[v][c]]) val[u]=1;
                 f[u]=ch[v][c];
             }
         }
     }
};

  

  

后缀自动机:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//后缀自动机SAM
struct  SAM {
     int  sz,last,fa[N],ch[N][26],l[N];
     SAM() {
         sz=0; last=++sz;
         memset (l,0, sizeof (l));
         memset (fa,0, sizeof (fa));
     }
     void  Add( int  c) {
         int  np=++sz,p=last; last=np;
         l[np]=l[p]+1;
         for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
         if (!p) fa[np]=1;
         else  {
             int  q=ch[p][c];
             if (l[q]==l[p]+1) fa[np]=q;
             else  {
                 int  nq=++sz; l[nq]=l[p]+1;
                 memcpy (ch[nq],ch[q], sizeof (ch[q]));
                 fa[nq]=fa[q];
                 fa[q]=fa[np]=nq;
                 for (;q==ch[p][c];p=fa[p]) ch[p][c]=nq;
             }
         }
     }
     //do some other things
     
} sam;

  

后缀数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//后缀数组
#define rep(a,b,c) for(int a=(b);a>=(c);a--)
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
char  s[N];
int  c[N],t[N],t2[N],height[N],rank[N],sa[N];
void  build_sa( int  m, int  n) {
     int  *x=t,*y=t2,p,k;
     FOR(i,0,m-1) c[i]=0;
     FOR(i,0,n-1) c[x[i]=s[i]]++;
     FOR(i,0,m-1) c[i]+=c[i-1];
     rep(i,n-1,0) sa[--c[x[i]]]=i;
     
     for (k=1;k<=n;k<<=1) {
         p=0;
         FOR(i,n-k,n-1) y[p++]=i;
         FOR(i,0,n-1)  if (sa[i]>=k) y[p++]=sa[i]-k;
         
         FOR(i,0,m-1) c[i]=0;
         FOR(i,0,n-1) c[x[y[i]]]++;
         FOR(i,0,m-1) c[i]+=c[i-1];
         rep(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
         
         swap(x,y);
         p=1; x[sa[0]]=0;
         FOR(i,1,n-1)
             x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]? p-1:p++;
         if (p>=n)  break ;
         m=p;
     }
}
void  get_height( int  n)
{
     FOR(i,0,n-1) rank[sa[i]]=i;
     int  k=0;
     FOR(i,0,n-1) {
         if (k) k--;
         int  j=sa[rank[i]-1];
         while (s[i+k]==s[j+k]) k++;
         height[rank[i]]=k;
     }
}

  

Manacher:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//Manacher算法
char  s[N],a[N];
int  p[N];
void  Add( int  l, int  r)
{
     l=l/2,r=r/2-1;
     if (l>r)  return  ;
     //q[++tot]=(Seg){l,r};
     //[l,r]为一个极大回文串
}
void  Manacher()
{
     int  n= strlen (s+1);
     int  m=n*2+1;
     for ( int  i=1;i<=n;i++) {
         a[i<<1]=s[i];
         a[i<<1|1]= '#' ;
     }
     a[0]= '+' ,a[1]= '#' ,a[m+1]= '-' ;
     int  mx=0,id;
     for ( int  i=1;i<=m;i++) {
         if (mx>i) p[i]=min(mx-i,p[id*2-i]);
         else  p[i]=1;
         while (a[i-p[i]]==a[i+p[i]]) p[i]++;
         Add(i-p[i],i+p[i]);
         if (p[i]+i>mx) mx=i+p[i],id=i;
     }
}

  

 

计算几何

 

计算几何基础知识:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//计算几何基础
 
const  double  eps = 1e-10;
int  dcmp( double  x) {
     if ( fabs (x)<eps)  return  0;  else  return  x<0? -1:1;
}
 
struct  Pt {
     double  x,y;
     Pt( double  x=0, double  y=0):x(x),y(y) {}
};
typedef  Pt vec;
 
vec operator - (Pt A,Pt B) {  return  vec(A.x-B.x,A.y-B.y); }
vec operator + (vec A,vec B) {  return  vec(A.x+B.x,A.y+B.y); }
vec operator * (vec A, double  p) {  return  vec(A.x*p , A.y*p); }
bool  operator < ( const  Pt& a, const  Pt& b) {
     return  a.x<b.x || (a.x==b.x && a.y<b.y);
}
bool  operator == ( const  Pt& a, const  Pt& b) {
     return  dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
}
 
double  cross(vec A,vec B) {  return  A.x*B.y-A.y*B.x; }
double  Dot(vec A,vec B) {  return  A.x*B.x+A.y*B.y; }
double  Len(vec A) {  return  sqrt (Dot(A,A)); }
double  Angle(vec A,vec B) {  return  acos (Dot(A,B)/Len(A)/Len(B)); }
 
//逆时针旋转rad角度
vec rotate(vec A, double  rad) {
     return  vec(A.x* cos (rad)-A.y* sin (rad) , A.x* sin (rad)+A.y* cos (rad));
}
//法向量 左转90度 长度归1
vec Normal(vec A)
{
     double  L=Len(A);
     return  vec(-A.y/L,A.x/L);
}
//判断点在线段上
bool  OnSeg(Pt P,Pt a1,Pt a2) {
     return  dcmp(cross(a1-P,a2-P))==0 && dcmp(Dot(a1-P,a2-P))<0;
}
//直线交点
Pt LineIntersection(Pt P,vec v,Pt Q,vec w) {
     vec u=P-Q;
     double  t=cross(w,u)/cross(v,w);
     return  P+v*t;
}
double  DistoLine(Pt P,Pt A,Pt B) {
     vec v1=B-A,v2=P-A;
     return  fabs (cross(v1,v2))/Len(v1);
}
//线段不含端点 判断相交
bool  SegIntersection(Pt a1,Pt a2,Pt b1,Pt b2) {
     double  c1=cross(a2-a1,b1-a1) , c2=cross(a2-a1,b2-a1) ,
            c3=cross(b2-b1,a1-b1) , c4=cross(b2-b1,a2-b1);
     return  dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
     // b1 b2在线段a1a2的两侧  a1 a2在线段b1b2的两侧  规范相交
}
//线段含端点 判断线段严格相交
bool  SegInter(Pt s1, Pt e1, Pt s2, Pt e2) {
     if ( min(s1.x, e1.x) <= max(s2.x, e2.x) &&
         min(s1.y, e1.y) <= max(s2.y, e2.y) &&
         min(s2.x, e2.x) <= max(s1.x, e1.x) &&
         min(s2.y, e2.y) <= max(s1.y, e1.y) &&
         cross(e1-s1,s2-s1) * cross(e1-s1,e2-s1) <= 0 &&
         cross(e2-s2,s1-s2) * cross(e2-s2,e1-s2) <= 0
       return  true ;
     return  false ;
}
//点到线段的距离
double  DistoSeg(Pt P,Pt A,Pt B) {
     if (A==B)  return  Len(P-A);
     vec v1=B-A , v2=P-A , v3=P-B;
     if (dcmp(Dot(v1,v2))<0)  return  Len(v2);
     else  if (dcmp(Dot(v1,v3))>0)  return  Len(v3);
     else  return  fabs (cross(v1,v2))/Len(v1);
}
//多边形面积
double  PolygonArea(Pt* p, int  n)
{
     double  S=0;
     for ( int  i=1;i<n-1;i++)
         S+=cross(p[i]-p[0],p[i+1]-p[0]);
     return  S/2;
}

  

凸包:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//凸包
const  int  N = 400000+10;
const  double  PI =  acos (-1.0);
const  double  eps = 1e-12;
 
int  dcmp( double  x) {
     if ( fabs (x)<eps)  return  0;  else  return  x<0? -1:1;
}
 
struct  Pt {
     double  x,y;
     Pt( double  x=0, double  y=0) :x(x),y(y) {};
};
typedef  Pt vec;
 
vec operator - (Pt a,Pt b) {  return  vec(a.x-b.x,a.y-b.y); }
vec operator + (vec a,vec b) {  return  vec(a.x+b.x,a.y+b.y); }
bool  operator == (Pt a,Pt b) {
     return  dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
}
bool  operator < ( const  Pt& a, const  Pt& b) {
     return  a.x<b.x || (a.x==b.x && a.y<b.y);
}
 
vec rotate(vec a, double  x) {
     return  vec(a.x* cos (x)-a.y* sin (x),a.x* sin (x)+a.y* cos (x));
}
double  cross(vec a,vec b) {  return  a.x*b.y-a.y*b.x; }
double  dist(Pt a,Pt b) {
     return  sqrt ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
 
vector<Pt> ConvexHull(vector<Pt> p) {
     sort(p.begin(),p.end());
     p.erase(unique(p.begin(),p.end()),p.end());
     int  n=p.size() , m=0;
     vector<Pt> ch(n+1);
     for ( int  i=0;i<n;i++) {
         while (m>1 && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
         ch[m++]=p[i];
     }
     int  k=m;
     for ( int  i=n-2;i>=0;i--) {
         while (m>k && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
         ch[m++]=p[i];
     }
     if (n>1) m--;
     ch.resize(m);  return  ch;
}

  

半平面交:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//半平面交
 
const  int  N =  305;
const  double  bond = 100001;
const  double  eps = 1e-10;
 
struct  Pt {
     double  x,y;
     Pt ( double  x=0, double  y=0):x(x),y(y){}
};
typedef  Pt vec;
 
vec operator + (Pt a,Pt b) {  return  vec(a.x+b.x,a.y+b.y); }
vec operator - (Pt a,Pt b) {  return  vec(a.x-b.x,a.y-b.y); }
vec operator * (Pt a, double  p) {  return  vec(a.x*p,a.y*p); }
 
double  cross(Pt a,Pt b) {  return  a.x*b.y-a.y*b.x; }
 
struct  Line {
     Pt p; vec v;  double  ang;
     Line () {}
     Line (Pt p,vec v) :p(p),v(v){ ang= atan2 (v.y,v.x); }
     bool  operator < ( const  Line& rhs)  const  {
         return  ang<rhs.ang;
     }
};
 
bool  onleft(Line L,Pt p) {  return  cross(L.v,p-L.p)>0; }
Pt LineInter(Line a,Line b)
{
     vec u=a.p-b.p;
     double  t=cross(b.v,u)/cross(a.v,b.v);
     return  a.p+a.v*t;
}
vector<Pt> HPI(vector<Line> L)
{
     int  n=L.size();
     sort(L.begin(),L.end());
     int  f,r;
     vector<Pt> p(n) , ans;
     vector<Line> q(n);
     q[f=r=0]=L[0];
     for ( int  i=1;i<n;i++) {
         while (f<r&&!onleft(L[i],p[r-1])) r--;
         while (f<r&&!onleft(L[i],p[f])) f++;
         q[++r]=L[i];
         if ( fabs (cross(q[r].v,q[r-1].v))<eps) {
             r--;
             if (onleft(q[r],L[i].p)) q[r]=L[i];
         }
         if (f<r) p[r-1]=LineInter(q[r-1],q[r]);
     }
     while (f<r&&!onleft(q[f],p[r-1])) r--;
     if (r-f<=1)  return  ans;
     p[r]=LineInter(q[r],q[f]);
     for ( int  i=f;i<=r;i++) ans.push_back(p[i]);
     return  ans;
}

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值