这么水的题比赛居然没有发现.....还是对C以上的题有心里阴影??
题目描述:
要求一笔划画出N(N<100)个五角形,输出方案(画的轨迹)。
算法分析:
将五角星一字排开,先从左向右画一个横,再从右向左画回来就可以了。
#include<complex>
#include<iostream>
#include<cstdio>
using namespace std;
#define X real
#define Y imag
typedef complex<double> pnt;
pnt p[1000];
int ans[2000];
int len , N,n;
const double pi = acos(-1.0);
const double sd = cos(36.0/180*pi)*10*2;
const double ag = 2*asin(5/sd);
struct pol{
int p[5];
} num[200];
void dfs(int tp,const pnt& s) {
if(tp == n) return ;
num[tp].p[0] = tp;
// 5
p[len] = pnt(X(s)+ sd, Y(s));
num[tp].p[1] = len;
ans[N++] = len++;
dfs(tp+1,p[len-1]);
// 6
p[len] = pnt(X(p[tp+1]) - cos(ag)*sd, Y(p[tp+1]) - sin(ag)*sd);
num[tp].p[2] = len;
ans[N++] = len++;
// 7
p[len] = pnt(X(p[len-1]) + sin(ag/2)*sd, Y(p[len-1]) + cos(ag/2)*sd);
num[tp].p[3] = len;
ans[N++] = len++;
// 8
p[len] = pnt(X(p[len-1]) + sin(ag/2)*sd, Y(p[len-1]) - cos(ag/2)*sd);
num[tp].p[4] = len;
ans[N++] = len++;
ans[N++] = tp;
}
int main(){
ans[0] =0;
p[0] = pnt(0,0);
while(cin >> n){
N = len = 1;
dfs(0,p[0]);
cout<<len<<endl;
for(int i=0;i<len;i++)
printf("%.11lf %.11lf\n",X(p[i]), Y(p[i]));
for(int i=0;i<n;i++) {
int *p = num[i].p;
for(int j=0;j<5;j++) num[i].p[j]++;
cout<<p[0]<<" "<<p[3]<<" "<<p[1]<<" "<<p[4]<<" "<<p[2]<<endl;
}
for(int i=0;i<N;i++)
cout<<ans[i]+1<<" ";cout<<endl;
}
}
posted on 2012-08-06 22:25
西月弦 阅读(288)
评论(0) 编辑 收藏 引用 所属分类:
解题报告