一些使用 Andrew 算法的解法没有考虑到:如果凸包是一条线,那么判断凸包条件时没有取等的代码(即一条线上中间的点都保留)的数组需要开两倍。
数据生成方式很简单,代码如下:
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("data.in","w",stdout);
int n=1e5;
printf("%d\n",n);
for(int i=1;i<=n;++i)
printf("%d %d\n",i,0);
return 0;
}
(答案应为 199998.00)
用这组数据可以卡掉 @Rainy7 ,@人殇物已非 等人的题解代码,建议将其加入本题数据,并建议对这样的题解进行修改。