結果

問題 No.2953 Maximum Right Triangle
ユーザー osada-yumosada-yum
提出日時 2024-11-16 01:02:53
言語 Fortran
(gFortran 13.2.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,661 bytes
コンパイル時間 1,611 ms
コンパイル使用メモリ 32,256 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-16 01:02:56
合計ジャッジ時間 1,170 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 1 ms
6,820 KB
testcase_06 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

!> This file was processed by `fypp`.
!> Today's fortune: "Lucky:)", really OK?
!> ランダムウォーク猿「'重実装' で はっぴー.」
program f902953
  use, intrinsic :: iso_fortran_env
  !> auto use module
  implicit none
  integer(int32) :: t
  integer(int32) :: i
  read(input_unit, *) t
  do i = 1, t
     call solve()
  end do
contains
  impure subroutine solve()
    integer(int64) :: d, x, y
    integer(int64) :: g, nx, ny
    read(input_unit, *) d, x, y
    if (x == 0) then
       write(output_unit, '(i0)') y * d
       return
    else if (y == 0) then
       write(output_unit, '(i0)') x * d
       return
    end if
    !> (nx, ny) == (y, -x) /g ベクトルは (x, y) ベクトルに垂直.
    g = gcd(x, y)
    nx =   y / g
    ny = - x / g
    block
      !> (x, y)
      !> nx >= 0.
      !> x + t * nx <= d.
      integer(int64) :: ans
      integer(int64) :: bx, by
      integer(int64) :: n_dist_sq
      n_dist_sq = nx ** 2 + ny ** 2
      ans = 0_int64
      if (nx < 0) then
         nx = - nx
         ny = - ny
      end if
      associate(t => (d - x) / nx)
        !> x + t * nx <= d
        if (t > 0) then
           bx = x + t * nx
           by = y + t * ny
           if (0 <= by .and. by <= d) then
              ans = max(ans, t * g * n_dist_sq)
           end if
        end if
      end associate

      associate(t => x / nx)
        !> x - t * nx >= 0
        if (t > 0) then
           bx = x - t * nx
           by = y - t * ny
           if (0 <= by .and. by <= d) then
              ans = max(ans, t * g * n_dist_sq)
           end if
        end if
      end associate

      if (ny < 0) then
         nx = - nx
         ny = - ny
      end if
      associate(t => (d - y) / ny)
        !> y + t * ny <= d
        if (t > 0) then
           bx = x + t * nx
           by = y + t * ny
           if (0 <= bx .and. bx <= d) then
              ans = max(ans, t * g * n_dist_sq)
           end if
        end if
      end associate

      associate(t => y / ny)
        !> y - t * ny >= 0
        if (t > 0) then
           bx = x - t * nx
           by = y - t * ny
           if (0 <= bx .and. bx <= d) then
              ans = max(ans, t * g * n_dist_sq)
           end if
        end if
      end associate
      write(output_unit, '(i0)') ans
    end block
  end subroutine solve

  pure integer(int64) function gcd(a, b) result(res)
    integer(int64), intent(in) :: a, b
    integer(int64) :: arr(1:2)
    arr(1:2) = [max(abs(a), abs(b)), min(abs(a), abs(b))]
    do while (arr(2) /= 0)
       arr(1:2) = [arr(2), mod(arr(1), arr(2))]
    end do
    res = arr(1)
  end function gcd
end program f902953
0