FFT模板
FFT
位逆序置换
1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>using namespace std;const double PI = acos(-1.0);struct Complex{ double real, imag;};void change(Complex y[], int len){ for (int i = 1, j = len / 2, k; i < len - 1; i++) { if (i < j) swap(y[i], y[j]); k = len / 2; while (j >= k) { j = j - k; k = k / 2; } if (j < k) ...
凸包
凸包
Anderw
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<iostream>#include<cstdio>#include<cmath>#include<algorithm> using namespace std;const int N = 1e5+10;const double eps = 1e-8;int n,top;double ans;struct point{ double x,y; point(){} point(double a,double b){x = a, y = b;}}p[N],sta[N];point operator + (point a,point b){return point(a.x+b.x,a.y+b.y);}point operator ...
计算几何模板
计算几何模板
处理精度判断正负
1234567const double eps = 1e-8;int dcmp(double x)//处理精度，判断正负 { if(fabs(x) < eps) return 0; if(x < 0) return -1; return 1;}
定义
点或向量
1234567891011struct point//点或向量{ double x,y; point(double X = 0, double Y = 0){x = X, y = Y;}};typedef point Vector//pair<double,double> ponit;double dis(point a,point b)//两点距离{ return (double) sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y))}
直线
12345struct Line{ point A,B; Line(point a,poin ...
spfA判断负环
负环
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include<bits/stdc++.h>using namespace std;#define MAX 1e9#define ll long longstruct edge{ int to; int nextE; ll w;};int head[2010];int num_edge[2010];int cnt=0;edge e[6010];ll dis[2010];int spfa(int n, int s){ bool vis[n + 1]; for (int i = 0; i <= n; i++) { vis ...
动态规划-其他
动态规划
流水线调度问题
12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;#define ll long longll minThree(ll a,ll b,ll c){ return min(min(a,b),c);}int main(){ int T; cin>>T; while(T--) { int m; cin>>m; vector<vector<ll>>p(3,vector<ll>(m+1)); for(int i=0; i<3; i++) for(int j=0; j<m; j++) cin>>p[i][j]; vector<vec ...
动态规划-背包
动态规划
01背包
123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;int main(){ int T; cin>>T; while(T--) { int n,V; cin>>n>>V; vector<int>bag(V+1); vector<int>w(n+1); vector<int>v(n+1); for(int i=0;i<n;i++) { cin>>w[i]>>v[i]; } for(int i=0;i<n;i++) { for(int j=V;j>=v[i]; ...
