Codeforces 1

a. theatre square:

        题目地址：

        题目大意：n*m的长方形用a*a的正方形覆盖，允许超出长方形，问需要几个正方形。

        算法讨论：计算长和宽分别需要几个a，相乘即可。

        code:

b. spreadsheets

        题目大意：将1, 2, 3, ...按a, b, c, ..., aa, ab, ...标号，完成这2种标号的相互转换。

        算法讨论：

                首先先判断读入的某行是哪个询问，只需判断有几个字符和前一个字符的种类不同即可。

                其次先是数字到字母的转化，将a..z看作1..26，然后看作26进制，将读入的26进制数转化乘10进制即可。

                然后是数字到字母的转化。设数字为x。对x作短除法的时候，若x%26==0，则对应的字母为‘z’，x=x/26-1；否则1..25对应的字母为‘a‘..‘y‘，x=x/26。

c. ancient berland circus

        题目大意：给出3个点，求最小面积的正多边形，使得这3个点为正多边形的顶点。

        算法分析：

                根据正多边形的性质，正多边形的每个顶点都在其外接圆上。

                已知3个点，可以根据海伦公式求出三角形的面积s。然后根据正弦定理求出外接圆的半径r=abc/(4s)，根据余弦定理求出三个圆心角。

                求出三个圆心角的最大公约数a，则正多边形由2*pi/a个小三角形组成。

                根据正弦定理求出每个小三角形的面积s0，则答案即为s0*2*pi/a。

by charlie pan

apr 30,2014