Codeforces Beta Round #1 题解

Author : Houge

A - Theatre Square

题目大意：

　　用

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     long long n,m,a;
 8     scanf("%lld%lld%lld",&n,&m,&a);
 9     n%a==0?n/=a:n=n/a+1;
10     m%a==0?m/=a:m=m/a+1;
11     printf("%lld",n*m);
12     return 0;
13 }

A-Theatre Square

B - Spreadsheets

题目大意：

　　两种表示excel表格的方式RXCY（第X行第Y列）、AB23（AB表示列，23表示行）的相互转换。

分析：

　　简单的字符串模拟，简要说一下相互转换的实现过程：

·数据的读入：

　　既然是两种类型，我们就要分类型来讨论，判断类型的依据就是有几组连续的字母，一组即为AB23类型，另一组为RXCY类型。

·RXCY→AB23:

　　我们要读入的是X和Y，其中Y不用做改变，就是转换后的列数。而对于X的变化相当于转化成由A~Z表示的26进制，但是要注意对Z要进行特判，如26行应是Z而不是AA。

·AB23→RXCY：

　　同上，23不用做改变，将AB转换成数字即可。

代码：

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 int main()
  6 {
  7     int t;
  8     scanf("%d",&t);
  9     getchar();
 10     while(t--)
 11     {
 12         //int mod=456976;
 13         string pos;
 14         int i,flag=0,mode=0,len;
 15         getline(cin,pos);
 16         len=pos.length();
 17         for(i=0;i<len;i++)    //输入，并判断是哪种表示形式
 18         {
 19             if(!(isalpha(pos[i]))) flag=1;
 20             if(isalpha(pos[i]))
 21             {
 22                 if(flag)
 23                 {
 24                     mode=1;
 25                     break;
 26                 }
 27             }
 28             mode=2;
 29             //cout<<mode<<endl;
 30         }
 31         if(mode==2)    //AB23
 32         {
 33 
 34             int column=0,row=0,pn,temp;
 35             for(i=0;i<len;i++)    //寻找中间位置
 36                 if(!isalpha(pos[i]))
 37                 {
 38                     pn=--i;
 39                     break;
 40                 }
 41             //cout<<pn<<'*'<<endl;
 42             temp=1;
 43             for(i=pn;i>=0;i--)    //AB->int 数字
 44             {
 45                 column+=(pos[i]-'A'+1)*temp;
 46                 temp*=26;
 47             }
 48             temp=1;
 49             for(i=len-1;i>pn;i--)    //char->int
 50             {
 51                 row+=(pos[i]-'0')*temp;
 52                 temp*=10;
 53             }
 54             printf("R%dC%d
",row,column);
 55         }
 56         if(mode==1)    //RXCY
 57         {
 58             int pc,row=0,column=0,temp;
 59             for(i=1;i<len;i++)    //寻找中间位置
 60                 if(pos[i]=='C')
 61                 {
 62                     pc=i;
 63                     break;
 64                 }
 65             temp=1;
 66             for(i=len-1;i>pc;i--)    //char -> int
 67             {
 68                 column+=(pos[i]-'0')*temp;
 69                 temp*=10;
 70             }
 71             temp=1;
 72             //cout<<pc<<endl;
 73             for(i=pc-1;i>0;i--)    //同上
 74             {
 75                 row+=(pos[i]-'0')*temp;
 76                 temp*=10;
 77             }
 78             stack<char> otp;    //实现int数字转换成AB形式，相当于26进制，但需特判Z的情况，并用stack维护实现先进后出
 79             do
 80             {
 81                 int y=column%26;
 82                 if(y!=0)
 83                 {
 84                     otp.push(char(y-1+'A'));
 85                     column/=26;
 86                 }
 87                 else
 88                 {
 89                     otp.push('Z');
 90                     column/=26;
 91                     column--;
 92                 }
 93             }while(column);
 94 
 95             while(!otp.empty())
 96             {
 97                 putchar(otp.top());
 98                 otp.pop();
 99             }
100             printf("%d
",row);
101         }
102     }
103     return 0;
104 }

B-Spreadsheets

C - Ancient Berland Circus

题目大意：

　　给定一个正多边形的三个顶点，求这个正多边形的最小面积。

分析：

　　简单的计算几何，过程打在注释里了。

代码：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const double eps=1e-4;
 6 
 7 double gcd(double a,double b)    //求实数的最小公因数
 8 {
 9     while(fabs(a)>eps&&fabs(b)>eps)
10     {
11         if(a>b) a-=floor(a/b)*b;
12         else b-=floor(b/a)*a;
13     }
14     return a+b;
15 }
16 
17 int main()
18 {
19     double x1,x2,x3,y1,y2,y3;
20     cin>>x1>>y1>>x2>>y2>>x3>>y3;
21     double a=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
22     double b=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1));
23     double c=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
24     double p=(a+b+c)/2;
25     double S=sqrt(p*(p-a)*(p-b)*(p-c));    //^^^^海伦公式求面积
26     double R=a*b*c/(4*S);    //求外接圆半径
27     double A=acos((b*b+c*c+-a*a)/(2*b*c));
28     double B=acos((a*a+c*c+-b*b)/(2*a*c));
29     double C=acos((b*b+a*a+-c*c)/(2*b*a));    //^^^^余弦定理求角
30     double PI=atan2(0,-1);
31     double n=PI/gcd(gcd(A,B),C);    //2Π除以圆心角的最小公因数得到最多边的边数
32     double ans=n/2*R*R*sin(2*PI/n);    //正弦定理求正多边形面积
33     printf("%.8f",ans);
34     return 0;
35 }

C-Ancient Berland Circus