Minimal, copy-paste Java for combinatorics (nCk mod P) and 2D geometry primitives (cross product, point on segment).
Contents
Combinatorics (nCk mod P)
int MOD=1'000'000'007; int N=200000;
static long modexp(long a,long e){ long r=1%MOD; while(e){ 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)
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