题意是，折纸，每次都从左边向右边折，折n次，最后展开，要求输出折痕。 可以发现，i次的折痕称为Zi，Zi是由Z(i-1)加上Z(i-1)相对折痕终点顺时针旋转90度两部分构成的。那么我们记录下所有的方向角度，
int acnt=0; ang[acnt++]=0, ang[acnt++]=1; for(int i=2;i<=n;i++){ int s=(1<<(i-1)); for(int j=s-1;j>=0;j--) ang[acnt++]=(ang[j]+1)%4; }假定折痕起点为(0,0)，那么根据所有方向角度，我们可以得到所有线段，注意横向的方向向量应该是(±2，0），即横坐标应当扩大一倍。因为_的特征x坐标值=(左右端点x值之和)/2，不扩大两倍将出现小数。 另外，竖线|的特征y坐标=下端点的y坐标，因为“|”中“”和“|”要出现在同一行上。 至此，处理完里所有线段，根据特征x坐标和特征y坐标排序即可，y降序，x增序。依次输出即可。
#include<map>#include<cmath>#include<ctime>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#define LL long longusing namespace std;const int maxn=10005;const LL Inf=1e18;int n;int ang[maxn];struct Point{ int x, y; Point(){} Point(int _x,int _y):x(_x), y(_y){} Point Operator + (const Point &rhs)const{ return Point(x+rhs.x, y+rhs.y); }};struct Line{ Point s, t; int vx, vy; Line(){} Line(Point _s, Point _t):s(_s), t(_t){}};Point dp[4]={Point(2,0), Point(0,1), Point(-2,0), Point(0,-1)};Line L[maxn];bool cmp(Line &A,Line &B){ if(A.vy==B.vy) return A.vx<B.vx; return A.vy>B.vy;}void solve(){ int acnt=0; ang[acnt++]=0, ang[acnt++]=1; for(int i=2;i<=n;i++){ int s=(1<<(i-1)); for(int j=s-1;j>=0;j--) ang[acnt++]=(ang[j]+1)%4; } L[0]=Line(Point(0,0),Point(0,0)+dp[0]); L[0].vx=(L[0].s.x+L[0].t.x)/2; L[0].vy=L[0].s.y; int minx, maxx; int miny, maxy; minx=maxx=L[0].vx; miny=maxy=L[0].vy; for(int i=1;i<acnt;i++){ Point sp=L[i-1].t; L[i]=Line(sp,sp+dp[ang[i]]); if(ang[i]%2){ L[i].vx=L[i].s.x; L[i].vy=min(L[i].s.y,L[i].t.y); }else{ L[i].vx=(L[i].s.x+L[i].t.x)/2; L[i].vy=L[i].s.y; } minx=min(minx,L[i].vx); maxx=max(maxx,L[i].vx); miny=min(miny,L[i].vy); maxy=max(maxy,L[i].vy); } sort(L,L+acnt,cmp); int sx, sy; sy=maxy; sx=minx; for(int i=0;i<acnt;i++){ if(L[i].vy<sy){ puts(""); sy--; sx=minx; i--; continue; } while(sx<L[i].vx){ PRintf(" "); sx++; } if(L[i].s.x==L[i].t.x) printf("|"); else printf("_"); sx++; } printf("/n^/n");}int main(){// freopen("matrix.in","r",stdin);//从in.txt中读取数据// freopen("matrix.out","w",stdout);//输出到out.txt文件 while(~scanf("%d",&n)&&n){ solve(); } return 0;}新闻热点
疑难解答
