Algorithm Templates: Math & Geometry
Minimal, copy-paste Java for combinatorics (nCk mod P) and 2D geometry primitives (cross product, point on segment).
Contents
Combinatorics (nCk mod P)
| ID | Title | Link | Solution | |—|—|—|—| | 62 | Unique Paths | Link | Solution | | 172 | Factorial Trailing Zeroes | Link | - |
int MOD=1'000'000'007; int N=200000;
static long modexp(long a,long e){ long r=1%MOD; while (e > 0) { if(e 1) r=r a%MOD; a=a a%MOD; e>>=1; } return r; }
long[]fact(N+1), invfact(N+1);
static void initComb(){ fact[0]=1; for(int i=1;i<=N;++i) fact[i]=fact[i-1]*i%MOD; invfact[N]=modexp(fact[N], MOD-2); for(int i=N;i>0;--i) invfact[i-1]=invfact[i]*i%MOD; }
static long nCk(int n,int k){ if(k<0||k>n) return 0; return fact[n]*invfact[k]%MOD invfact[n-k]%MOD; }
| ID | Title | Link | Solution |
|---|---|---|---|
| 62 | Unique Paths | Link | Solution |
| 172 | Factorial Trailing Zeroes | Link | - |
Geometry Primitives (2D)
| ID | Title | Link | Solution | |—|—|—|—| | 149 | Max Points on a Line | Link | - | | 223 | Rectangle Area | Link | - | | 1344 | Angle Between Hands of a Clock | Link | Solution |
class P{ long x,y; }
long cross(P a,P b,P c){ return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); }
boolean onSeg(P a,P b,P c){ return Math.min(a.x,b.x)<=c.x&&c.x<=Math.max(a.x,b.x)&&Math.min(a.y,b.y)<=c.y&&c.y<=Math.max(a.y,b.y) && cross(a,b,c)==0; }
| ID | Title | Link | Solution |
|---|---|---|---|
| 149 | Max Points on a Line | Link | - |
| 223 | Rectangle Area | Link | - |
| 1344 | Angle Between Hands of a Clock | Link | Solution |
More templates
- DP (counting, paths): Dynamic Programming
- Data structures, Graph, Search: Data Structures & Core Algorithms, Graph, Search
- Master index: Categories & Templates