[JAVA] 백준 2304, 창고 다각형

https://www.acmicpc.net/problem/2304

---

처음으로 제출했을 때 오답처리가 되었다. 그 이유는 왼쪽 x좌표 -> 오른쪽 x좌표로만 고려를 했기 때문이다.

 

이 문제는 왼쪽 -> 오른쪽 탐색, 오른쪽 -> 왼쪽 탐색 두 번을 수행해야 한다. 

물론 여기서 끝에서 끝까지 탐색하는 것이 아닌, 중간 인덱스를 찾아야 한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static class Point {

        int x, y;

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

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        List<Point> points = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            points.add(new Point(l, h));
        }

        Collections.sort(points, (p1, p2) -> {
            return p1.x - p2.x;
        });

        int area = 0;

        Point prev = points.get(0);
        int midIdx = 0;
        for (int i = 1; i < points.size(); i++) {
            Point cur = points.get(i);

            if (cur.y >= prev.y) {
                area += (cur.x - prev.x) * prev.y;
                prev = cur;
                midIdx = i;
            }
        }

        prev = points.get(points.size() - 1);
        for (int i = 1; i < points.size() - midIdx; i++) {
            Point cur = points.get(points.size() - 1 - i);

            if (cur.y >= prev.y) {
                area += (prev.x - cur.x) * prev.y;
                prev = cur;
            }
        }

        area += points.get(midIdx).y;

        System.out.println(area);
    }
}