#1
有n个物品，每个物品有重量wi和体积vi且密度均匀。你可以切物品，每次可以选一个物品切成两部分，也就是选一个0到1的实数k把物品分成k和(1-k)比例的两个物品。
你有最多X次切的机会。
问题1. 要想保证切完之后一定能把物品分成两组使得两组重量和相等，体积和也相等，X至少是几。
ans1.
(1) 把体积看成长度用一个环拼在一起，然后考虑旋转直径来划分，这样保证了长度的情况下用了界值定理。
(2) 用糖水浓度考虑，原始人想法。
(3) 二维平面用y表示密度，体积为长度，单调队列考虑
问题2. 设计高效算法求问题1的方案。
问题3. 如果是分成三组呢
问题0. 如果是要把物品分成两组使得两组数量相同且体积和也相等呢（不考虑重量）。
主要是考虑界值定理的应用
#2
对一个序列a[1]...a[n]，找一个位置x，使得a[1]+...+a[x]和a[x+1]+...+a[n]的比值在[1/c,c]之间，要求c尽可能小
问题1. c最大情况下是多少，并构造对应c的例子
ans1. 对应带权分治。最坏卡到inf
问题2. 如果允许将某一个a[i]原位切开成两个相邻的位置，这两个位置的权值加起来是a[i]且任意分配，c最大情况下是多少，当n很大并且a[i]>=1的情况下，c会变小吗？
ans2. 1：2 ，具体卡到就是 {1,2}。不然就正常分治。
对一棵n个点的树，找一条边，使得这条边断开后，两边的连通子图的比值在[1/c,c]之间
问题3. c最大情况下是多少，并构造对应c的例子
ans3. 1：n 菊花图。
问题4. 如果树是一棵二叉树，对任意一个给定的n，c最大情况下是多少，并给出一个通用的构造对应c的例子的算法
ans4. 1：2 考虑调整法，二度即可往右边走，三度就选最大的走。卡到的话就是一个中心，然后三个等大的部分。
在树的基础上，如果给定一个结点x，将x删去后剩下若干个连通子图，将这些连通子图分成两组，使得两组点数的比值在[1/c,c]之间，要求c尽可能小
问题5. c最大情况下是多少，并构造对应c的例子
ans5. (可以爆炸）
问题6. 如果结点x是你自己选定的，c最大情况下是多少，并构造一个通用算法
ans6. 肯定是找树的重心。可以将树三度话，具体的可能类似于kruskal重构树。也可以用哈夫曼树来证明。1：2
对应问题：树分治。
#3
二维平面上有n个点，要求这些点互相不重合，并且三点不共线，编号为1...n，现在我们要画一条直线，如果一个点(x,y)满足Ax+By+C>=0，则视为点(x,y)在直线Ax+By+C=0的上方。将直线上方的点看做是一个集合。
问题1.如果n个点的坐标由你来构造，对直线Ax+By+C=0，假设A,B,C取遍所有实数，最多可以得到多少个不同的集合
ans1.可以先平移再旋转，然后卡住两个点。
问题2.如果有若干条直线，其上方点的集合相同，是否可以通过对这些直线进行旋转和平移，使得这些直线变成同一条直线
ans2. 同1
问题3.如果改变你在问题1中构造的点的坐标，不同的集合数是否会发生改变
ans3. 同1
问题4.给定点(x,y)，对于所有过(x,y)的直线，是否一定存在一条直线，使得直线两侧的点数最多只差1，这里的点数不统计(x,y)，如果点在直线上，由你决定属于哪一侧
ans4. 旋转边界值定理。
问题5.是否可以找到两条相交的直线，使得给定的n个点被分成四个点集，且最大的点集和最小的点集大小最多差1，如果点在直线上，由你决定属于哪一个点集
ans5. 给定一个已经等分的先，然后我们考虑给定相交线的角度 \(\alpha\) ，那么我们肯定可以通过平移来做到有一边平分，然后对于角度考虑界值定理。
问题6.是否可以找到三条共点的直线，使得给定的n个点被分成六个点集，且最大的点集和最小的点集大小最多差1，如果点在直线上，由你决定属于哪一个点集
（未完待续）
对应问题：平面四分树，平面六分树，可以做半平面修改。
标签：直线,个点,思考题,祖先,点集,问题,给定,公共,物品 From： https://www.cnblogs.com/tttxz/p/18431950