计算几何，积分

p2280，好多用二维前缀和的题目可以用扫描线的方法搞定

在讨论《题解hack》回复：

@[迟暮天复明](/user/222865) 可以把这组数据加入测试中。

在讨论《题解hack》回复：

@[迟暮天复明](/user/222865) 这个是该样例的说明，经过旋转后，显然中间有一大区域是没有交点的，从[-a,a]用自适应simpson积分有问题。 

在讨论《题解hack》回复：

@[迟暮天复明](/user/222865) 错误原因在于作者把积分区域设置为（-a，a）这样当三角形与椭圆仅在很窄一个区域内相交时，因为大部分区间的值域为0，会导致simpson的递归过程提前结束。

在讨论《题解hack》回复：

@[迟暮天复明](/user/222865) 就是椭圆与三角形相交区域的面积，这个测试数据显然不为0

P3219,一摸一样的题，除了数据范围

提供一组数据 输入 ```cpp -8 -97 -137 -240 965 -500 -210 -398 -474 -817 -64 ``` 正确输出 ```cpp 14342.10 ``` 题解输出0.0

在讨论《这个题有正解吗》回复：

@[__Thaumic_Executor__](/user/765382) 是啊，所以我在问有没有正解，对任意数据都有效，否则就是错题啊

在讨论《这个题有正解吗》回复：

@[scp020](/user/553625) ```cpp #include #include #include #include #include #include #include using namespace std; #define LOCAL 0 #define MAXN 20 const double…

在讨论《这个题有正解吗》回复：

@[scp020](/user/553625) 我还真就没用模拟退火或任何随机算法AC了，不过这没有任何意义。因为我卡时了。https://www.luogu.com.cn/record/160118777

在讨论《这个题应该是个错题》回复：

我用了CGA算法可以AC,但是应该无法对任意数据在规定时间内完成。 ```cpp #include #include #include #include #include #include #include using namespace std; #define LOCAL 0 #define MAXN 20 con…

应该不存在保证可以在规定时间内对任何数据都有效的算法。

在讨论《这个题有正解吗》回复：

@[lonely_seele](/user/226449) 他自己没多少经验还来质疑别人

在讨论《这个题有正解吗》回复：

@[lonely_seele](/user/226449) 这个人就是个垃圾。我问问有没有不依靠这种玄学或者不面向数据的算法有没有都不行

在讨论《这个题有正解吗》回复：

@[scp020](/user/553625) 你看来经验太少啊，模拟退火WA时候，参数调整是要下载看来然后再调整的，而不是瞎试。

在讨论《这个题有正解吗》回复：

@[scp020](/user/553625) 我用CompleteGreedyAlgorithm 还真就AC了，没用模拟退火。不过仍然不够完美。

在讨论《这个题有正解吗》回复：

@[scp020](/user/553625) 我难道是刚学模拟退火的萌新？你的退火初始温度，结束温度，退火速率难道不是面向数据编程得到的？

在讨论《这个题有正解吗》回复：

@[scp020](/user/553625) 你在比赛时看得到是否AC?你根本无法调整参数啊

怎么全是模拟退火或者随机贪心算法？有没有不是面向数据编程的普通算法？我用了dfs搜索只有80分

题解区怎么全是模拟退火算法？就没有不面向数据编程的普通算法吗？

m=6，模拟退火试了很多参数都不行啊

比如每个木板的长度在10^6以内，应该怎么求解呢？ DFS貌似很容易超时啊

该问题本质上是NP的，因此没有多项式算法，假设三角形边长都是int范围内的数，dp根本不可行。但是由于n<=40, 用dfs的meet-in-middle技巧，可以解决这个问题啊。如果不一定非要追求精确解的话，那么KK算法也可以使用

在讨论《这题有在线做法吗？》回复：

@[Tjaweiof](/user/550933) 干啥呢，最多就是出题咯

在讨论《这题有在线做法吗？》回复：

@[Tjaweiof](/user/550933) 能简要描述下不？

在讨论《这题有在线做法吗？》回复：

@[Tjaweiof](/user/550933) 你有idea？

在讨论《这题有在线做法吗？》回复：

@[xwh_Marvelous](/user/614527) 感觉不好弄，每个点需要维护的信息太多了，内存估计要爆炸

所谓在线就是查询某个用户的粮食数最多的那个种类与发放路径的粮食是交替进行的

在讨论《这个题根本卡不了平衡树啊》回复：

@[ppip](/user/374433) 先分裂，然后递归合并啊