洛谷 P14944 已经没有什么好构造的了 题解

不难发现凸多边形最多有 33 个锐角。因此对于 3m3 显然无解。否则分讨 m 的取值构造方法如下图所示红线代表一段凸壳。这样问题就变成了如何构造红色的凸壳部分。由于只能用整点因此凸壳中线段斜率均为有理数。这启发我们构造一串不同的正斜率并从大到小排序。具体做法就是枚举所有满足 1≤,≤1≤p,q≤K 的 qp​约分排序并去重。发现 406K406 时就能得到至少 105105 个不同斜率。我们还需要证明这样做不会超出 108108 的值域限制。由于凸壳中不超过 n 条线段每条线段对 ,x,y 坐标的贡献均 ≤≤K因此右上角的点的 ,x,y 坐标均不会超过 ≤4.06×107108nK≤4.06×107108证毕。注意特判掉 ≤4n≤4 的情况。Code#include bits/stdc.h #define rept(i,a,b) for(int i(a);ib;i) #define fi first #define se second #define pii pairint,int using namespace std; constexpr int K406,NK*K5; struct Frac{ int a,b; Frac(int _a0,int _b1):a(_a),b(_b){ int ggcd(a,b);a/g,b/g; } inline bool operator(const Frac rhs) const { return a*rhs.brhs.a*b; } inline bool operator(const Frac rhs) const { return arhs.abrhs.b; } }s[N]; int T,n,m,cnt; const vectorpii get_convex_hull(int e){ // 返回包含e条边左下角为(0,1)的凸壳上的点逆时针顺序 vectorpii res; pii cur(0,1); res.emplace_back(cur); rept(i,1,e){ cur.fis[i].a; cur.ses[i].b; res.emplace_back(cur); } reverse(res.begin(),res.end()); return res; } signed main(){ scanf(%d,T); rept(i,1,K) rept(j,1,K) s[cnt]Frac(i,j); sort(s1,scnt1); cntunique(s1,scnt1)-s-1; while(T--){ scanf(%d%d,n,m); if(n3){ switch(m){ case 2:printf(0 0\n1 0\n0 1\n);break; case 3:printf(0 0\n2 0\n1 2\n);break; default:printf(scare\n); } }else if(n4){ switch(m){ case 0:printf(0 0\n1 0\n1 1\n0 1\n);break; case 1:printf(1 0\n3 1\n1 2\n0 1\n);break; case 2:printf(1 0\n2 0\n0 2\n0 1\n);break; case 3:printf(3 0\n6 4\n3 5\n0 4\n);break; default:printf(scare\n); } }else{ vectorpii res; int x,y; switch(m){ case 0: resget_convex_hull(n-4); xres[0].fi,yres[0].se; printf(0 0\n%d 0\n%d %d\n,x1,x1,y); for(auto [x,y]:res) printf(%d %d\n,x,y); break; case 1: resget_convex_hull(n-4); xres[0].fi,yres[0].se; printf(0 0\n%d 0\n%d %d\n,x2,x1,y); for(auto [x,y]:res) printf(%d %d\n,x,y); break; case 2: resget_convex_hull(n-2); xres[0].fi,yres[0].se; printf(%d 1\n,x); for(auto [x,y]:res) printf(%d %d\n,x,y); break; case 3: resget_convex_hull(n-2); xres[0].fi,yres[0].se; printf(%d 1\n,x1); for(auto [x,y]:res) printf(%d %d\n,x,y); break; default: printf(scare\n); } } } return 0; }