Code Archive Index: =========================================================================== 2D Geometry: /2D_Geometry/ ------------------------ angle_2d.c Magnitude of angle (in radians) between 3 points angle_2d180.c Magnitude of angle (in radians) between 3 points v2 area_ellipse.c Area of an arbitrary ellipse in quadratic form area_heron.c Area of a triangle given lengths of three sides area_poly.c Signed area of a simple polygon area_regpoly.c Area of a regular N-gon with side length S area_tri.c Area of a triangle given its 3 vertices area_unionrect.c Area of a union of rectangles ccw.c Test if a->b->c is CW, CCW, or undefined centroid.c Finds the centroid (center of mass) of a polygon circ_3pts.c Origin and radius of circle given 3 points circ_tangents.c Given a point and circle, finds points of tangency closest_pair.c Finds closest pair of point from a set of point closest_pt_iline.c Find point on infinite line AB closest to point C closest_pt_lineseg.c Find point on line segment AB closest to point C convex_hull.c Convex hull of a set of points dist_2d.c Distance between two points dist_iline.c Shortest distance from a point to an infinite line isect_circ_area.c Area of intersection of two circles isect_circ_line.c Intersection pt(s) of circle and line/line segment isect_circ_pts.c Intersection points of two circles isect_circ_test.c Intersection status of two circles isect_iline.c Intersection pt of two infinite lines isect_lineseg.c Intersection pt of two line segments isect_lineseg_test.c Tests if two line segments intersect isect_poly_area.cc Area of intersection of two simple polygons laser.cc Simulate a laser bouncing off a mirror lat_poly_pick.c # of interor/boundary points on a lattice polygon max_empty_rect.cc Largest empty rectangle in W*H field with N points midpts2vert.c Finds a polygon given its midpoints min_circle.c Finds minimum bounding circle around set of points point_in_convex_poly.c Test if point is within convex polygon poly_similar.c Tests if two polygons are similar to one another pt_in_poly.c Test if a point is inside a polygon pt_leftright.c Test if point is left/right/collinear with line pts2_genline.c Given two points, returns the line Ax+By = C rect_in_rect_test.c Test if rectangle can fit inside another rectangle reflect.c Reflect a point across a given line rotate_2d.c Rotate a point around another point soddy_circ_radius.c Finds radius of Soddy circle given 3 radii triangulate.cc Triangulates a simple 2D polygon 3D Geometry: /3D_Geometry/ ------------------------ area_cpoly3d.c Finds the area of a planar convex polygon geom.cc Ashley's 3D-do it all library greatcircle.c Great circle distance between 2 points on a sphere sphere_from_4pts.c Calculates sphere defined by 4 points Arithmetic: /Arithmetic ------------------------ discrete_log.cc Solves discrete logarithms: b^x == n mod (prime p) fast_exp.c Calculates b^N in O(lg N) time simpsons.c Simpson's rule for numerical integration solve_cubic.c Solves cubic equations ax^3+bx^2+cx+d = 0 solve_quad.c Solve quadratic equations ax^2+bx+c = 0 t_func.c Find avg. number of trials to collect n pieces C++ ------------------------ maps.cc Maps template for C++ STL next_permutation.cc Next permutation generator from C++ STL pqueue.cc Priority queue template for C++ STL string_tokenizer.cc String tokenizer template for C++ Combinatorics: ------------------------ binomial.c Calculate binomial coefficients up to Choose(68,34) digit_count.c Counts number of times a digit occurs from 1..N factorial_dig.c Find the number of digits of N! in base B josephus.c Find the (n,m)-Josephus ring survivor necklace.c Find # of size-N necklaces/bracelets with K colors permdex_distinct.c Find permutation # for distinct-character strings Data Structures: /Data_Struct ------------------------ heap_static.c Heap implementation unionfind.c Efficient implementation of set union operations Dynamic Programming: /Dynamic ------------------------ asc_subseq.c Find longest [strictly] ascending subsequence asc_subseq2.c Longest ascending subsequence O(N^2) edit_dist.c Find the edit distance between two strings integer_partition.c Find the # of ways to partition N into M pos. ints long_common_subseq.c Find longest common subsequence between two arrays max_submatrix.c Find maximum submatrix sum Generators: /Generators ------------------------ catalan.c Generate catalan numbers n <= 33 gen_bin_card.c Generates binary strings based ordered by # of 1's gen_ksubset.c Generate subsets of size k, (lex, colex, minchange) nqueens.c Generate a solution for the N-Queens problem in O(N) pyth.c Generate pythagorean triples Graph Theory: /Graph_Theory/ ------------------------ articulation_pts.c Find nodes which disconnect a graph (adj.list) bellmanford.c Shortest path from a node, allowing negative weights bipartitematch.c Finds maximum matching in bipartite graph escape.c Generic escape problem solver euler.c Checks for Eulerian graphs, finds Euler paths/cycles euler_d.c Template for directed Eulerian graphs floyd.c Floyd's All-pairs shortest path maxflow.cc Find max flow in a directed graph O(|V|^2 * |E|) maxflow_v2.cc Find max flow in a directed graph O(|V|^3) maxflow_lb.cc Finds max flow in a network with upper/lower bounds min_span_tree2.c Finds a minimal spanning tree version 2 minpath_vertexcover.cc Min # vertex-disjoint paths covering acyclic digraph postman.c Solves the Chinese Postman problem scc_d_tour_kcycle.cc Find k-cycle in directed tournament graph stable.c Solves the stable marriage problem strong_conn.cc Finds strongly-connected components in digraphs top_sort.cc Find a topological sorting of a DAG tree_isomorph.cc Computes certificate for tree isomorphism Java /Java ------------------------ base_convert.java Convert numbers from one base to another BigDecimal.java BigDecimal template BigInteger.java BigInteger template IO.java Input output template Miscellaneous: /Misc/ ------------------------ bitcount.c Counts number of '1' bits in a number roman.cc Conversion between Roman and Arabic numbers rubik.c Rubik's cube simulator sqr_index.c Routines for square rotation/flipping strrev.c Reverses a string ud_find.cc Find smallest lex-first ambiguous message ud_test.cc Test if a set of codewords is uniquely decipherable Number Theory: /Num_theory/ ------------------------ binarygcd.c Find the gcd of two numbers (algorithm B) eulerphi.c Find # of natural numbers < N, relatively prime to N factinfact.c Finds how many factors of k in N! isprime.c Checks if a positive number N is prime num_divisors.c Calculates the number of positive divisors of N primefactor.c Find prime factorization of N, 2 <= N <= INT_MAX primes.c Generate array of primes up to N, primality testing primesieve.c Primality testing based on Sieve of Eratosthenes sum_divisors.c Calculates the sum of all positive divisors of N Parsing: /Parsing/ ------------------------ infix_eval.c Parse a simple infix math expression (+,-,*,/) infix_to_postfix.c Convert infix expression to postfix with prescedence parse_exp.cc Parse a simple infix math expression (+,-,*,/,^),vars Search: /Search/ ------------------------ binsearch.c Generalized binary search template cage.c Find minimum order (r-g) cages color.c Graph k-coloring template golden.c Golden section search (trinary search) hamming.cc Find maximal Hamming code template ortho_latin.c Finds sets of orthogonal Latin squares queen.c Find valid configurations for N non-attacking queens walk.c Find all self avoiding walks of length N word_search.c Find all occurences of some strings in text