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

Solution不难发现凸多边形最多有333个锐角。因此对于m3m3m3显然无解。否则分讨mmm的取值构造方法如下图所示红线代表一段凸壳。这样问题就变成了如何构造红色的凸壳部分。由于只能用整点因此凸壳中线段斜率均为有理数。这启发我们构造一串不同的正斜率并从大到小排序。具体做法就是枚举所有满足1≤p,q≤K1\le p,q\le K1≤p,q≤K的pq\frac{p}{q}qp​约分排序并去重。发现K406K406K406时就能得到至少10510^5105个不同斜率。我们还需要证明这样做不会超出10810^8108的值域限制。由于凸壳中不超过nnn条线段每条线段对x,yx,yx,y坐标的贡献均≤K\le K≤K因此右上角的点的x,yx,yx,y坐标均不会超过nK≤4.06×107108nK\le 4.06\times 10^710^8nK≤4.06×107108证毕。注意特判掉n≤4n\le 4n≤4的情况。Code#includebits/stdc.h#definerept(i,a,b)for(inti(a);ib;i)#definefifirst#definesesecond#definepiipairint,intusingnamespacestd;constexprintK406,NK*K5;structFrac{inta,b;Frac(int_a0,int_b1):a(_a),b(_b){intggcd(a,b);a/g,b/g;}inlinebooloperator(constFracrhs)const{returna*rhs.brhs.a*b;}inlinebooloperator(constFracrhs)const{returnarhs.abrhs.b;}}s[N];intT,n,m,cnt;constvectorpiiget_convex_hull(inte){// 返回包含e条边左下角为(0,1)的凸壳上的点逆时针顺序vectorpiires;piicur(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());returnres;}signedmain(){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){case2:printf(0 0\n1 0\n0 1\n);break;case3:printf(0 0\n2 0\n1 2\n);break;default:printf(scare\n);}}elseif(n4){switch(m){case0:printf(0 0\n1 0\n1 1\n0 1\n);break;case1:printf(1 0\n3 1\n1 2\n0 1\n);break;case2:printf(1 0\n2 0\n0 2\n0 1\n);break;case3:printf(3 0\n6 4\n3 5\n0 4\n);break;default:printf(scare\n);}}else{vectorpiires;intx,y;switch(m){case0: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;case1: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;case2: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;case3: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);}}}return0;}