【AtCoder】JavaでABC224のA,B,C問題を解く！

ABC224のA,B,C問題をJavaで解きました。
備忘録としてまとめておきます。

A問題『Tires』

問題ページ：A - Tires

入力

S : 文字列（末尾は「er」または「ist」、必ず 2文字以上）

コード

import java.util.*;
public class Main
 {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        //文字列の後方一致チェック
        if(str.endsWith("r"))
        {
            System.out.println("er");
        }else 
        {
            System.out.println("ist");
        }
    }
}   

B問題『Mongeness』

問題ページ：B - Mongeness

入力

縦 $H$ 行、横 $W$ 列のマス目（それぞれ最大 $50$）
上から $i$ 行目、右から $j$ 行目 には整数 $Ai,j$が書かれている

コード

import java.util.*;
public class Main
 {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        // 画面入力値を取得する
        // 縦行数と横行数を取得する
        int h = sc.nextInt();
        int w = sc.nextInt();

        // 各マス目の値を取得する　 
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                a[i][j] = sc.nextInt();
            }
        }


        for(int i1  = 0; i1 < h; i1++)
        {
            for(int i2 = i1 + 1; i2 < h; i2++)
            {
                for(int j1 = 0; j1 < w; j1++)
                {
                    for(int j2 = j1 + 1; j2 < w; j2++)
                    {
                        // 成立しない場合
                        if(a[i1][j1] + a[i2][j2] > a[i2][j1] + a[i1][j2])
                        {
                            System.out.println("No");
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("Yes");
    }
 }        

4重ループですべての $i_1<i_2$ および $j_1<j_2$ を満たす $(i_1,i_2,j_1,j_2)$ の組を全探索して、すべての組が
$A_{i_1,j_1}+A_{i_2,J_2}≤A_{i_2,j_1}+A_{i_1,j_2} $

を満たすかを確認する。

C問題『Triangle?』

問題ページ：C - Triangle?

入力

$N$ : 点の数
$Xi$,$Yi$ : 点 $i$ の座標（整数）

コード

import java.util.*;
public class Main
 {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        // 画面入力値を取得する
        int n = sc.nextInt();
        // 座標を取得する
        int[][] a = new int[n][2];

        for(int i = 0; i < n; i++)
        {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt(); 
        }

        int cnt = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = i +1; j < n; j++)
            {
                for(int k = j + 1; k < n; k++)
                {
                    // 3点が一直線上に並んでいない場合
                    int x1 = a[i][0], x2 = a[j][0], x3 = a[k][0];
                    int y1 = a[i][1], y2 = a[j][1], y3 = a[k][1];
                    if((y2 - y1)*(x3 - x1) != (y3 - y1)*(x2 - x1))
                    {
                        cnt ++; 
                    }
                }
            }
        }

        System.out.println(cnt);
    }
}

『選ばれた 3 点を線分で結んだ図形が正の面積を持つ三角形になる』
この条件を満たさない場合を考える。
⇒『3点が一直線上に並んでいる時』面積のある三角形にならない。

選んだ 3 点 $A,B,C$ の座標をそれぞれ $A(x1,y1)$、$B(x2,y2)$、$C(x3,y3)$とすると、
『$3$ 点が一直線上に並んでいる』状態は、線分 $AB$ と $AC$ の傾きが等しい場合である。
数式で表すと

$\frac{y_2−y_1}{x_2−x_1}=\frac{y_3−y_1}{x_3−x_1}$

分母を払って
$(y_2−y_1)×(x_3−x_1)=(y_3−y_1)×(x_2−x_1)$

よって、
3重ループで3点の組を全検索して、3点が一直線上に並んでいる場合を除けばよい。