Skip to content

Instantly share code, notes, and snippets.

View jacky860226's full-sized avatar

jacky860226

67 followers · 7 following
View GitHub Profile
@jacky860226
jacky860226 / decode.cpp
Created June 14, 2019 12:18
Lempel–Ziv–Welch (LZW) c++ implement
#include<vector>
#include<string>
#include<map>
using namespace std;
string decode(const vector<int> &v){
map<int,string> inv_dict;
int dictSize = 256;
for(int i=0;i<dictSize;++i)
inv_dict[i] = string(1,i);
string s, entry, res;
@jacky860226
jacky860226 / steinerTreeBuilder.h
Created March 23, 2019 09:24
A Faster Approximation Algorithm for the Steiner Tree Problem in Graphs
/***********************************************************************************
From <<A Faster Approximation Algorithm for the Steiner Tree Problem in Graphs>>
Kurt MEHLHORN
O(N logN) 2-approximation
Implement: SunMoon Master(Jinkela SHENGDIYAGE)
************************************************************************************/
#pragma once
@jacky860226
jacky860226 / DelaunayDivideAndConquer.cpp
Last active February 6, 2019 14:52
Delaunay Triangulation
template<class T>
class Delaunay{
struct PT:public point<T>{
int g[2];
PT(const point<T> &p):
point<T>(p){ g[0]=g[1]=-1; }
};
static bool cmp(const PT &a,const PT &b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
@jacky860226
jacky860226 / HV.cpp
Last active December 31, 2018 15:23
Longest Common Cyclic Subsequence
#include<cstring>
#include<algorithm>
const int MAXN=1505;
int h[MAXN][MAXN*2], v[MAXN][MAXN*2];
char B[MAXN*2];
int CLCS(const char *a, const char *b){
int m = strlen(a), n = strlen(b);
strcpy(B,b); strcpy(B+n,b);
for(int j=0; j<n*2; ++j) h[0][j] = j+1;
for(int i=0; i<m; ++i){
@jacky860226
jacky860226 / convexBST.cpp
Created December 23, 2018 16:30
lower convex hull self-balancing binary search tree
#include<map>
using std::map;
using std::pair;
#define x first
#define y second
template<typename T>
class convexBST : public map<T,T>{
typedef const pair<T,T>& point;
static T cross(point a, point b, point c){
return (a.x-c.x) * (b.y-c.y) - (b.x-c.x) * (a.y-c.y);
@jacky860226
jacky860226 / simplex.h
Last active November 30, 2018 16:59
simplex algorithm
#include<vector>
#include<algorithm>
using namespace std;
template<class VDB>
VDB simplex(int m,int n,vector<VDB> a){
vector<int> left(m+1), up(n+1);
iota(left.begin(), left.end(), n);
iota(up.begin(), up.end(), 0);
auto pivot = [&](int x, int y){
swap(left[x], up[y]);
@jacky860226
jacky860226 / pdf.html
Last active November 28, 2024 12:00
PDF.js
<!DOCTYPE html>
<html dir="ltr" mozdisallowselectionprint>
<head>
<meta charset="utf-8">
<title>PDF.js viewer</title>
<!-- pdf.js v2.0.332 -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/pdf.js/2.0.332/pdf.min.js"></script>
</head>
<body tabindex="1" class="loadingInProgress">
@jacky860226
jacky860226 / symmetric_minmax_heap.cpp
Created February 14, 2018 08:18
Symmetric Min-Max Heap v2.0
#ifndef SUNMOON_SYMMETRIC_MIN_MAX_HEAP
#define SUNMOON_SYMMETRIC_MIN_MAX_HEAP
#include<vector>
#include<algorithm>
template<typename T,typename _Seq=std::vector<T>,typename _Compare=std::less<T> >
class symmetric_minmax_heap{
_Seq s;
_Compare cmp;
void BubbleUp(size_t id){
if(id%2&&cmp(s[id],s[id-1])){
@jacky860226
jacky860226 / st_queue.cpp
Last active January 11, 2018 15:17
stack implement queue
#include<vector>
template<typename T>
class st_queue{
std::vector<T> A,B;
public:
void swap(st_queue& stq){
A.swap(stq.A);
B.swap(stq.B);
}
bool empty()const{
@jacky860226
jacky860226 / SM_sort.cpp
Created October 18, 2017 15:46
medians of medians
template<typename IT,typename CMP>
void SM_sort(IT first,IT last,CMP cmp){ // 幫他寫了一個sort做測試
if(last-first<=1)return;
IT mid=kth(first,last,(last-first)/2,cmp);
SM_sort(first,mid,cmp);
SM_sort(mid+1,last,cmp);
}