글 읽기 - 72%에서 틀립니다 도와주세요~

alreadyj 5년 전 0

코사인 값 이용해서 정렬하고

일직선인 경우도 체크했지만 ... 안되네요

import java.io.*;
import java.util.*;

public class Main {
    private static int n, minY = 40001, minIndex = -1;
    private static List<Point> points = new ArrayList<>();
    private static String[] ins;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            ins = br.readLine().split(" ");
            int curY = Integer.parseInt(ins[1]);
            points.add(new Point(Integer.parseInt(ins[0]), curY));
            if (curY < minY) {
                minY = curY;
                minIndex = i;
            }
        }
        bw.write(getCountOfPointInConvexHull() + "\n");
        bw.flush();bw.close();
    }

    private static int getCountOfPointInConvexHull() {
        Stack<Point> s = new Stack<>();
        Point minPoint = points.get(minIndex);
        boolean isCurve = false;
        points.remove(minIndex);
        Comparator<Point> pointComparator = (p1, p2) -> {
            double size1, size2;
            double cos1 = getCosine(p1, minPoint);
            double cos2 = getCosine(p2, minPoint);
            if (cos1 < cos2) {
                return 1;
            } else if (cos1 == cos2) {
                size1 = Math.pow(p1.x - minPoint.x, 2) + Math.pow(p1.y - minPoint.y, 2);
                size2 = Math.pow(p2.x - minPoint.x, 2) + Math.pow(p2.y - minPoint.y, 2);
                return (cos1 >= 0 && cos1 < 1) ? -Double.compare(size1, size2) : Double.compare(size1,  size2);
            } else {
                return -1;
            }
        };
        points.sort(pointComparator);
        s.push(minPoint);
        s.push(points.remove(0));
        Point cur, prev, next;
        do {
            cur = s.pop();
            prev = s.peek();
            next = points.get(0);
            int ccw = ccw(prev, cur, next);
            if (ccw > 0) {
                s.push(cur);
                s.push(next);
                points.remove(0);
                isCurve = true;
            } else if (ccw == 0) {
                s.push(next);
                points.remove(0);
            }
        } while (s.size() >= 2 && points.size() > 0);
        cur = s.pop();
        prev = s.peek();
        next = minPoint;
        return (ccw(prev, cur, next) == 0 && isCurve) ? s.size() : s.size() + 1;
    }

    private static double getCosine(Point p, Point minPoint) {
        double hypotenuse, base;
        hypotenuse = Math.sqrt(Math.pow(p.x - minPoint.x, 2) + Math.pow(p.y - minPoint.y, 2));
        base = p.x - minPoint.x;
        return base / hypotenuse;
    }

    private static int ccw(Point p1, Point p2, Point p3) {
        long ccw = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - p1.y * p2.x - p2.y * p3.x - p3.y * p1.x;
        return Long.compare(ccw, 0L);
    }

    private static class Point {
        long x, y;
        private Point(long x, long y) {
            this.x = x; this.y = y;
        }
    }
}

akswnd98 5년 전 0

저도 72%에서 틀립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

72%에서 틀립니다 도와주세요~

alreadyj 5년 전 0

akswnd98 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말