[USACO] Triangles JAVA

문제

www.acmicpc.net/problem/18786

풀이 및 코드

import java.util.Scanner;

public class Main {

    // USACO Triangles
    // 백준 18786
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Fence[] fences = new Fence[n];

        //펜스 입력
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            fences[i] = new Fence(x, y);
        }

        // 모든 삼각형의 경우를 구해서 제일 큰 삼각형을 찾자
        // 말뚝 a,b,c 를 골랐을 때 삼각형의 넓이를 구하자
        int max = 0; //출력할 삼각형 넓이
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                for (int c = 0; c < n; c++) {

                    Fence f1 = fences[a];
                    Fence f2 = fences[b];
                    Fence f3 = fences[c];

                    // 펜스가 하나라도 중복이 있다면 continue
                    if (a == b || a == c || b == c) continue;

                    // a,b,c 가지고 삼각형 넓이 구하자
                    // 한 삼각형은 꼭짓점이 3개 이므로,
                    // abc , acb , bac , bca , cab , cba 이렇게 6가지 경우로 나올 수 있다.
                    // 그래봤자 6개 모두 같은 삼각형이므로 원하는 형태의 삼각형에 대해 계산을 해준다.
                    if (f1.x == f2.x && f1.y == f3.y) {
                        int temp = Math.abs(f1.y - f2.y) * Math.abs(f1.x - f3.x);   //if 의 조건에서 f1,f2 의 x가 같은 경우 이므로 f1,f2,의 y로 계산한다.
                        max = temp > max ? temp : max;
                    }
                }
            }
        }

        System.out.println(max);

    }//main

}//class

//펜스
class Fence {
    int x;
    int y;

    public Fence(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Fence{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

 

삼각형이 다음과 같이 선택될 수 있으므로
이 중 원하는 형태의 삼각형을 선택하여 넓이를 구한다.