首页 > ACM题库 > HDU-杭电 > HDU 1439 Cipher-计算几何[解题报告] C++
2013
12-10

HDU 1439 Cipher-计算几何[解题报告] C++

Cipher

问题描述 :

Bob and Alice started to use a brand-new encoding scheme. Surprisingly it is not a Public Key Cryptosystem, but their encoding and decoding is based on secret keys. They chose the secret key at their last meeting in Philadelphia on February 16th, 1996. They chose as a secret key a sequence of n distinct integers, a1 ; . . .; an, greater than zero and less or equal to n. The encoding is based on the following principle. The message is written down below the key, so that characters in the message and numbers in the key are correspondingly aligned. Character in the message at the position i is written in the encoded message at the position ai, where ai is the corresponding number in the key. And then the encoded message is encoded in the same way. This process is repeated k times. After kth encoding they exchange their message.

The length of the message is always less or equal than n. If the message is shorter than n, then spaces are added to the end of the message to get the message with the length n.

Help Alice and Bob and write program which reads the key and then a sequence of pairs consisting of k and message to be encoded k times and produces a list of encoded messages.

输入:

The input file consists of several blocks. Each block has a number 0 < n <= 200 in the first line. The next line contains a sequence of n numbers pairwise distinct and each greater than zero and less or equal than n. Next lines contain integer number k and one message of ascii characters separated by one space. The lines are ended with eol, this eol does not belong to the message. The block ends with the separate line with the number 0. After the last block there is in separate line the number 0.

输出:

Output is divided into blocks corresponding to the input blocks. Each block contains the encoded input messages in the same order as in input file. Each encoded message in the output file has the lenght n. After each block there is one empty line.

样例输入:

10
4 5 3 7 2 8 1 6 10 9
1 Hello Bob
1995 CERC
0
0

样例输出:

BolHeol b
C RCE

http://acm.hit.edu.cn/hoj/problem/view?id=1439

给出三个点坐标 计算过这三个点的圆的周长

利用a/sinA=2R和S=0.5*bcsinA计算 S可用叉乘算

#include <stdio.h>
#include <math.h>

const double pi = acos(-1);
double find_r(double x1, double y1, double x2, double y2, double x3, double y3);

int main()
{
    double r, c;
    double x1, y1, x2, y2, x3, y3;
    
    while (scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3) != EOF)
    {
        r = find_r(x1, y1, x2, y2, x3, y3);
        c =2 * pi * r;
        printf("%.2lf\n", c);
    }
    
    return 0;
}


double find_r(double x1,double y1,double x2,double y2,double x3,double y3)
{
    double s,r,a,b,c;
    
    s = fabs(0.5 * ((x1-x3) * (y2-y3) - (x2-x3) * (y1-y3)));
    a = sqrt(pow((x1-x2), 2) + pow((y1-y2), 2));
    b = sqrt(pow((x1-x3), 2) + pow((y1-y3), 2));
    c = sqrt(pow((x3-x2), 2) + pow((y3-y2), 2));
    r = (a*b*c) / (4*s);
    return r;
}

 

解题报告转自:http://blog.csdn.net/epk_lee/article/details/8232424


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  4. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  5. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?