50桶水，其中1桶有毒。有n头猪，一天可以喝两次水，请问在一天内可以找出有毒的那桶水的最小的n。
同leetcode 458
有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下：
选择若干活猪进行喂养可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
重复这一过程，直到时间用完。
给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的最小猪数。
一头猪可以有\(x= minutesToTest / minutesToDie + 1\) 种状态，n头猪可以表示的信息一共有\(x^n\)。具体操作为：每次喂每头猪n进制编号下该位数为i的水
一个绳子随机剪成三段，求能让这三段组成三角形的概率
用二元一次不等式组表示 x，y， n的关系， 画图求面积， 最终1/4
50个红球与50个白球，放入两个盒子，要求每个盒子至少有一个球。拿的时候随机在其中一个盒子内，随机拿出一个球。请问如何摆放这些球，让拿出的是红球的概率最大
一个盒子放一个红球， 另一个盒子放剩余99个球，此时摸红球概率最大，接近于0.75
一个椭球体\((\frac{x^2}{a^2} +\frac{y^2}{b^2}+\frac{z^2}{c^2} =1)\)内接长方体的最大体积
拉格朗日乘数法，
其中，\((x, y, z)\) 为内接长方体在第一象限与椭球体的交点坐标， 求解，
在2-D plane, 检查一个点是否在一个三角形内（四个点给定）
1. 内角和等于360°
这种方法最好理解，即对于△ABC内的某一点P，连接PA、PB、PC得到三条线段，当且仅当三条线段组成的三个夹角和为360°的时候，该点才位于三角形内部。但此种方法的计算涉及到平方根、反正（余）弦，效率十分低下。
类似的还有，P与ABC三个顶点组成的三个三角形，面积之和等于△ABC的面积，同样可以证明点P位于三角形内部，但效率也很低。
2. Same Side Technique
这种方法是我从别处看来的，觉得很新颖，想看英文原版的可以直接点这里。下面我解释一下该方法的思想，首先看下图：
如果某点位于△ABC内部，那么该点一定位于AB的下边，AC的右边，BC的左边。要用数学的方法来表示，可以采用向量积，向量积有个很重要的右手定则。下面接着看下一张图：
对于任意的一点P, \(\vec{AB} \times \vec{AP}\)，其结果根据右手定则，应为指向屏幕外，而\(\vec{AB} \times \vec{AP^{'}}\)的结果则是指向屏幕里。根据这一特性，我们只要找到某一点\(P\)，满足\(\vec{AC} \times \vec{AB}\)与\(\vec{AC} \times \vec{AP}\)具有同一方向、\(\vec{CB} \times \vec{CA}\)与\(\vec{CB} \times \vec{CP}\)具有同一方向、\(\vec{BA} \times \vec{BC}\)与\(\vec{BA} \times \vec{BP}\)具有同一方向，则点P位于△ABC内。
这种方法涉及到的计算是向量运算，没有平方根、反余弦这些，效率比第2种方法高，代码部分
class Point2D(object):
def __init__(self, x=None, y=None):
self.x = x
self.y = y
def __sub__(self, other):
res = Point2D()
res.x = self.x - other.x
res.y = self.y - other.y
return res
def cross_product_2d(a: Point2D, b: Point2D) -> float:
return a.x * b.y - a.y * b.x
def same_side(v: Point2D, v1: Point2D, v2: Point2D) -> bool:
cp1 = cross_product_2d(v, v1)
cp2 = cross_product_2d(v, v2)
return cp1 * cp2 > 0
def in_triangle(p: Point2D, a: Point2D, b: Point2D, c: Point2D) -> bool:
AB, AC, AP = b-a, c-a, p-a
BA, BC, BP = a-b, c-b, p-b
CB, CA, CP = b-c, a-c, p-c
if same_side(AC, AP, AB) and same_side(BA, BC, BP) and same_side(CB, CA, CP):
return True
else:
return False
3. Barycentric Coordinates
最后一种方法的效率最高，但是理解起来需要的步骤多一点，我们先看下面这张图
\(\vec{AP}\)可以表示为
其中u、v为常量系数，从图中我们即可得知，当u>0且v>0时，P的位置才有可能正确，那是不是u、v可以无限大呢？当然不是，当u+v>1时，P就会超出三角形的范围，而当u+v=1时，点P刚好位于BC上，这里稍微证明一下。
当点P在BC上时，也就是 \(\vec{BP},\vec{PC}\)同向，将前面 \(\vec{AP}\)的表示方式代入，那么这两个向量可以分别表示为：
由于两者同向，那么就存在一个$ λ( λ>0)\(，使得\) \vec{BP}=λ\vec{PC}$，代入上面两式，整理一下，就得到了下面的式子：
上式要成立，当且仅当左右两边的系数都为0。由此得到两个方程，消去 λ就可以得到u+v=1了。有了这一点，为什么三角形内部点的u、v之和小于1，外部点的大于1，请读者自行理解，这里不再展开了。
由此我们的模型就得到了：对于任意给定的一点P，判断其是否位于△ABC的内部，就是要计算其相对于△ABC的u、v值，只要这两个值满足u>0、 v>0、 u+v<1，那么可以确定点P位于三角形内。这样只要得到u、v的表达式，在代码里面就能直接使用了。
// Compute vectors
v0 = C - A
v1 = B - A
v2 = P - A
// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)
// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom
// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v < 1)
计算2-D凸多边形面积
思路
可以将凸多边形（边数n > 3）划分为 (n - 2) 个三角形，分别运用向量叉积计算每个三角形的面积，最后累加各个三角形的面积就是多边形的面积。
class Point(object):
def __init__(self, x, y):
self.x = x
self.y = y
# 计算三角形面积
def getS(a: Point,b:Point, c:Point) -> float:
# 应用叉积的定义推出的
area = ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) / 2
return area
#计算多边形面积。必须确保 n>=3，且多边形是凸多边形
def getPS(p:List[Point], n:int) -> float:
sumS = 0
for i in range(1, n):
#n-2个三角形的面积和
sumS += getS(p[1], p[i], p[i + 1])
return sumS