算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
这么水的题比赛居然没有发现.....还是对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)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理