Skip to content

Instantly share code, notes, and snippets.

View kaikai2's full-sized avatar

Zikai Zhang kaikai2

View GitHub Profile
@kaikai2
kaikai2 / dynamic_battlefog.cpp
Last active December 17, 2015 23:29
在一个平面格子地图中,求从一个点为视点中心,指定半径范围可见区域的多边形。 按角度排序所有潜在可见边的两个端点,端点按扫描方向分为开始端点和结束端点。 从一个最近的端点开始扫描, 每当遇到一个开始端点就把它所属的可见边加入当前扫描集中,并判断这个端点与当前可见边相比是否更近(远的被挡住直接无视)更近的话添加一个射线与当前边的交点然后切换当前边。 每当遇到一个结束端点,就从当前扫描集中去掉这个端点所属的边,然后找当前射线与所有当前扫描集的交点中最近的作为新的当前边。同时添加结束端点以及射线与新的扫描边的交点到结果多边形。 扫描过程最多执行2圈,直到新添加的多边形点已经在结果多边形(闭合)为止。 如果需要一个指定的夹角,那么扫描开始和结束的角度射线作为起止条件即可。
#include "dynamic_battlefog.h"
#include <cmath>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
using std::max;
using std::min;
CDynamicBattleFog::CDynamicBattleFog()
@kaikai2
kaikai2 / findijk.cpp
Created March 29, 2013 07:36
StartFragment#面试编程题# Given a array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]. Could you find possible in O(n) algorithm. http://weibo.com/1915548291/zpuaLlfh5EndFragment
#include <cstdio>
#include <vector>
#include <assert.h>
using namespace std;
vector<int> getLeftMin(const vector<int> &vecAll)
{
vector<int> vecMin;
if (!vecAll.empty())
{
@kaikai2
kaikai2 / max_consecutive_sequence_len.cpp
Last active December 14, 2015 14:29
@陈利人: #面试编程题#Given an unsorted array of integers, find the length of the longest consecutive ele\ ments sequence. Eg, given [100, 2, 1, 3], The longest consecutive elements sequence is [1, 2, 3].\ Return its length: 3. Your algorithm should run in O(n). (谢谢 @张成_ICT 推荐)
#include <cstdio>
#include <vector>
#include <ext/hash_map>
#include <algorithm>
using namespace std;
using namespace __gnu_cxx;
typedef pair<int,int> pairii;
int max_consecutive_sequence_len(const vector<int> &vecArray)
{
@kaikai2
kaikai2 / 5.7-a-b.lisp
Last active December 13, 2015 21:28
;定义一个接受一系列数字的函数,并在若且唯若每一对(pair)数字的差为一时,返回真,使用 ;(a) 递归 ;(b) do
;http://acl.readthedocs.org/en/latest/zhCN/ch5-cn.html#chapter-5-exercises
;定义一个接受一系列数字的函数,并在若且唯若每一对(pair)数字的差为一时,返回真,使用
;(a) 递归
;(b) do
(defun linked-r (lst)
(or (null lst)
(null (cdr lst))
(and (diff-1 (car lst) (cadr lst))
(linked-r (cdr lst)))))
@kaikai2
kaikai2 / 5.7-c.lisp
Last active December 13, 2015 21:28
; http://acl.readthedocs.org/en/latest/zhCN/ch5-cn.html#chapter-5-exercises
; 5.7-c
; 定义一个接受一系列数字的函数,并在若且唯若每一对(pair)数字的差为一时,返回真,使用mapc 与 return。
(defun linked-mapc (lst)
(mapc #'(lambda (x y)
(unless (diff-1 x y)
(return-from linked-mapc nil)))
lst (cdr lst))
t)
@kaikai2
kaikai2 / pab.cpp
Last active December 10, 2015 02:39
A丢100个6面骰子,B丢160个4面骰子。那么A的点数总和比B的点数总和大的几率以及相等的几率分别该怎么计算? http://weibo.com/2039631434/zaMYL2jOj
/*
A丢100个6面骰子,B丢160个4面骰子。那么A的点数总和比B的点数总和大的几率以及相等的几率分别该怎么计算?
http://weibo.com/2039631434/zaMYL2jOj
*/
#include <cstdio>
#include <cassert>
template<int n,int dice>
double f(int d)
{