Skip to content

Instantly share code, notes, and snippets.

Avatar

Takanori MAEHARA spaghetti-source

View GitHub Profile
View Saizeria.ipynb
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
View coloring.lp
node(sendai;ishinomaki;shiogama;kesennuma;shiroishi;natori;kakuda;tagajyo;iwanuma;tome;kurihara;higashimatsushima;oosaki;zaou;shichikasyuku;oogawara;murata;shibata;kawasaki;marumori;watari;yamamoto;matsushima;shichigahama;rifu;taiwa;oosato;tomiya;oohira;shikama;kami;wakuya;misato;onagawa;minamisanriku).
edge(sendai,natori). edge(sendai,tagajyo). edge(sendai,tomiya). edge(sendai, murata). edge(sendai, kawasaki). edge(sendai, shichigahama). edge(sendai, rifu). edge(sendai, taiwa). edge(sendai, shiki).
edge(ishinomaki, tome). edge(ishinomaki, higashimatsushima). edge(ishinomaki, wakuya). edge(ishinomaki, misato). edge(ishinomaki, onagawa). edge(ishinomaki, minamisanriku).
edge(shiogama, tagajyo). edge(shiogama, shichigahama). edge(shiogama, rifu).
edge(kesennuma, tome). edge(kesennuma, minamisanriku).
edge(shiroishi, kakuda). edge(shiroishi, zaou). edge(shiroishi, shichikasyuku). edge(shiroishi, oogawara). edge(shiroishi, marumori).
edge(natori, sendai). edge(natori, kesennuma). edge(natori, murata).
edge(kaku
@spaghetti-source
spaghetti-source / bentley-ottman.cc
Created Dec 29, 2017
Bentley-Ottman Segment Intersection O((n+k) log n)
View bentley-ottman.cc
#include <iostream>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <map>
#include <cassert>
#include <queue>
#include <set>
@spaghetti-source
spaghetti-source / branch_bound_HK.cc
Created Feb 8, 2015
TSP branch bound with Held-Karp lower bound
View branch_bound_HK.cc
//
// Held and Karp bound
//
// T が 1-tree iff T は {2,...,n} 上の全域木 + 1 から枝が 2 本.
// 1-tree かつ全部の頂点の誘導次数が 2 であればそれはサイクル.
//
// 巡回セールス人を
// minimize c(T)
// subject to T is a 1-tree
// deg_T(i) = 2 for all i
View assignment.cc
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cmath>
#include <cstring>
#include <functional>
#include <algorithm>
#include <unordered_map>
@spaghetti-source
spaghetti-source / network.tex
Created Nov 28, 2014
pgfplots network drawing sample
View network.tex
\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{positioning,arrows,calc}
\usepackage{pgfplots}
\begin{document}
%%%
\tikzstyle{node}=[draw=black,circle,inner sep=0,minimum size=10]
\def \nodes {
1/-5/8.6,
@spaghetti-source
spaghetti-source / dominance.cc
Created Nov 24, 2014
Dominance problems (red-blue dominance and colorless dominance)
View dominance.cc
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cmath>
#include <cstring>
#include <functional>
#include <algorithm>
#include <unordered_map>
View vanttage_point_tree.cc
//
// Vantage Point Tree (vp tree)
//
// each node has two childs, left and right;
// the left childs are closer than the threshold,
// and the right childs are farther than the thoreshold.
//
#include <iostream>
#include <vector>
#include <cstdio>
View randomized_kd_tree.cc
//
// Randomized KD Tree (for d = 2)
//
// even split/join require O(n) time; however
// insert/remove require only O(log n) time.
//
#include <iostream>
#include <cstdio>
#include <complex>
@spaghetti-source
spaghetti-source / loadeddice.cc
Last active Aug 29, 2015
Draw a number [0...n) from a loaded dice (Vose's alias method)
View loadeddice.cc
//
// Draw a number [0...n) from a loaded dice (Vose's alias method)
//
#include <iostream>
#include <vector>
using namespace std;
unsigned int xor32() {
static unsigned long y = 2463534242UL;