Skip to content

Instantly share code, notes, and snippets.

View jacky860226's full-sized avatar

jacky860226

67 followers · 8 following
View GitHub Profile
@jacky860226
jacky860226 / Basic.cpp
Last active August 14, 2021 01:36
Segment Intersection
template <typename T> struct point {
T x, y;
point() {}
point(const T &x, const T &y) : x(x), y(y) {}
point operator+(const point &b) const { return point(x + b.x, y + b.y); }
point operator-(const point &b) const { return point(x - b.x, y - b.y); }
point operator*(const T &b) const { return point(x * b, y * b); }
bool operator==(const point &b) const { return x == b.x && y == b.y; }
T dot(const point &b) const { return x * b.x + y * b.y; }
T cross(const point &b) const { return x * b.y - y * b.x; }
@jacky860226
jacky860226 / snake.py
Last active December 27, 2019 08:17
python easy snake
import copy
import pygame,sys,time,random
from pygame.locals import *
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __eq__(self, other):
return self.x==other.x and self.y==other.y
@jacky860226
jacky860226 / kruskal.cpp
Last active August 2, 2019 06:18
Minimum Spanning Tree
template<typename T>
class kruskal{
static const int MAXN=100005;
int n; // 1-base
tuple<T,int,int> edge;
int pa[MAXN];
int find(int x){
if(x==pa[x]) return x;
return pa[x] = find(pa[x]);
}
@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">