本题题解区中 @zero4338 的题解的修改操作每次暴力修改凸包最大值点,其最坏时间复杂度为 O(n),因此他的最坏的总时间复杂度为 O(n2),然而却通过了本题,请求管理员添加 hack 数据。
数据生成:
#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=1e5;
bool flag;
int main(){
//freopen("input.txt","w",stdout);
printf("%d\n",maxn);
for(ri i=1;i<=maxn;++i)printf("%d ",maxn-i+1);
printf("\n%d\n",maxn);
for(ri i=1;i<=maxn;++i){
if(i%3==0)printf("1 %d %d\n",1,maxn);
else printf("0 %d %d %d\n",1,maxn,(flag^=1)?-maxn:maxn);
}
return 0;
}
(顺带一提第一篇和第四篇题解在这组数据下都跑的挺慢的