AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC402-D Line Crossing
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("8 3");
WillReturn.Add("1 5");
WillReturn.Add("1 8");
WillReturn.Add("2 4");
//2
}
else if (InputPattern == "Input2") {
WillReturn.Add("5 10");
WillReturn.Add("2 5");
WillReturn.Add("1 5");
WillReturn.Add("1 2");
WillReturn.Add("2 4");
WillReturn.Add("2 3");
WillReturn.Add("1 3");
WillReturn.Add("1 4");
WillReturn.Add("3 5");
WillReturn.Add("3 4");
WillReturn.Add("4 5");
//40
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
decimal[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => decimal.Parse(pX)).ToArray();
SplitAct(InputList[0]);
decimal N = wkArr[0];
decimal M = wkArr[1];
var CntDict = new Dictionary<decimal, decimal>();
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
decimal FromPos = wkArr[0];
decimal ToPos = wkArr[1];
decimal Hou = N / 2;
decimal Mid = (FromPos + ToPos) / 2;
while (Hou <= Mid) {
Mid -= Hou;
}
if (CntDict.ContainsKey(Mid) == false) {
CntDict[Mid] = 0;
}
CntDict[Mid]++;
}
decimal Answer = M * (M - 1) / 2;
foreach (decimal EachDec in CntDict.Values) {
Answer -= EachDec * (EachDec - 1) / 2;
}
Console.WriteLine(Answer);
}
}
解説
考察すると、弧上の中点が一致すれば、
平行であると分かります。
弧上の中点では、円周の半分を法として、
法未満になるまで引き算してます。