计算几何模板
计算几何模板
处理精度判断正负
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]; ...
honer规则/大数相乘/快速幂
杂项
秦久韶算法/honer规则
123456789101112ll sum(int n, vector<int> &a, int x){ ll ans = 0; ll mid = 1; for (int i = 0; i <= n; i++) { ans = (ans + (a[i] % MOD * mid % MOD) % MOD) % MOD; mid = (mid * x) % MOD; } return ans;}//带入x求f(x);f(x)=a0*x0+a1*x1...
大数相乘
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<iostream>#include<string>using namespace std;//移位进位法string Mul(stri ...
堆和单调栈
数据结构
堆
注意：这些函数中num为形参。(懒得写指针了)
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include<stdio.h>void heapUp(int *heap,int index){ while(index>0) { int parent=(index-1)/2; if(heap[parent]<heap[index]) { int mid=heap[index]; heap[index]=heap[parent]; heap[parent]=mid; index=parent; } els ...
