AGC036-A Triangle

問題へのリンク

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("3");
            //1 0 2 2 0 1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("100");
            //0 0 10 0 0 10
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("311114770564041497");
            //314159265 358979323 846264338 327950288 419716939 937510582
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long S = long.Parse(InputList[0]);

        long X1 = 1000000000;
        long Y2 = S / X1;
        if (S % X1 > 0) Y2++;
        long X2 = 1;
        long Y1 = -S + X1 * Y2;

        Console.WriteLine("0 0 {0} {1} {2} {3}", X1, Y1, X2, Y2);
    }
}

解説

三角形の面積は、ベクトルの外積を使って求めることが可能です。

3点の内の1点は原点として考えると
三角形の面積は、残りの2点の座標を(X1,Y1) , (X2,Y2) として
X1*Y2 - X2*Y1 の絶対値 / 2 となります。

なので
X1*Y2 - X2*Y1 = S
を満たす X1,Y1,X2,Y2
を求めれば良いと分かります。

後は、
X1 を 10の9乗
X2 を 1
Y2 を (S / X1) の端数切り上げ
として解を求めることができます。