AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC292-F Regular Triangle Inside a Rectangle
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("1 1");
//1.03527618041008295791
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static double mWidth;
static double mHeight;
struct PointDef
{
internal double X;
internal double Y;
}
static void Main()
{
List<string> InputList = GetInputList();
double[] wkArr = InputList[0].Split(' ').Select(pX => double.Parse(pX)).ToArray();
double A = wkArr[0];
double B = wkArr[1];
mWidth = Math.Min(A, B);
mHeight = Math.Max(A, B);
double Result = ExecSanbuntansaku();
Console.WriteLine(Result);
}
// 三分探索で極大値を求める
static double ExecSanbuntansaku()
{
double L = 0;
double R = 30;
while (L + double.Epsilon < R) {
double BeforeL = L, BeforeR = R;
double C1 = (L * 2 + R) / 3;
double C2 = (L + R * 2) / 3;
double C1Val = DeriveVal(C1);
double C2Val = DeriveVal(C2);
if (C1Val > C2Val) {
R = C2;
if (R == BeforeR) break;
}
else {
L = C1;
if (L == BeforeL) break;
}
}
var MaxKouhoList = new List<double>();
MaxKouhoList.Add(DeriveVal(L));
MaxKouhoList.Add(DeriveVal(R));
return MaxKouhoList.Max();
}
// 角度を引数として、正三角形の1辺の長さを返す
static double DeriveVal(double pKakudo)
{
PointDef Point2;
Point2.X = mWidth;
Point2.Y = mWidth * Math.Tan(DeriveRad(pKakudo));
if (Point2.Y > mHeight) return 0;
double Sin60 = Math.Sin(DeriveRad(60));
double Cos60 = Math.Cos(DeriveRad(60));
PointDef Point3 = Exec1JiHenkan(Point2, Sin60, Cos60);
if (Point3.Y > mHeight) return 0;
if (Point3.X < 0) return 0;
return Math.Sqrt(Point2.X * Point2.X + Point2.Y * Point2.Y);
}
// 度数法の角度をラジアンに変換
static double DeriveRad(double pDo)
{
return pDo * Math.PI / 180;
}
// ベクトルとSinとCosを引数として、回転したベクトルを返す
static PointDef Exec1JiHenkan(PointDef pPos, double pSin, double pCos)
{
PointDef WillReturn;
WillReturn.X = pCos * pPos.X + pPos.Y * -pSin;
WillReturn.Y = pSin * pPos.X + pPos.Y * pCos;
return WillReturn;
}
}
解説
長方形を、横幅 <= 縦幅
としてから、座標で考えることにします。
(0,0)に正三角形の左下の頂点として、
2つ目の頂点までの角度は、0度から30度の間ですので、
この角度を三分探索してます。
極大値が一つしかないので、三分探索できます。