#23189 (Java21) No.199 星を描こう

• 問題: No.199 星を描こう
• ユーザー: thorikawa
• 提出日時: 2015-04-29 00:08:28
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 137 ms / 2,000 ms
• コード長: 9,279 bytes
• コンパイル時間: 4,567 ms
• コンパイル使用メモリ: 86,636 KB
• 実行使用メモリ: 56,188 KB
• 最終ジャッジ日時: 2023-08-28 18:33:53
• 合計ジャッジ時間: 8,364 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	133 ms; 55,708 KB
testcase_01	AC	133 ms; 56,020 KB
testcase_02	AC	132 ms; 56,100 KB
testcase_03	AC	132 ms; 56,004 KB
testcase_04	AC	133 ms; 55,520 KB
testcase_05	AC	132 ms; 56,028 KB
testcase_06	AC	131 ms; 55,960 KB
testcase_07	AC	132 ms; 55,588 KB
testcase_08	AC	132 ms; 55,948 KB
testcase_09	AC	132 ms; 55,720 KB
testcase_10	AC	136 ms; 55,712 KB
testcase_11	AC	130 ms; 55,884 KB
testcase_12	AC	130 ms; 55,708 KB
testcase_13	AC	130 ms; 56,048 KB
testcase_14	AC	133 ms; 55,764 KB
testcase_15	AC	129 ms; 55,772 KB
testcase_16	AC	132 ms; 55,516 KB
testcase_17	AC	133 ms; 56,144 KB
testcase_18	AC	131 ms; 55,720 KB
testcase_19	AC	131 ms; 55,584 KB
testcase_20	AC	136 ms; 55,960 KB
testcase_21	AC	137 ms; 55,544 KB
testcase_22	AC	134 ms; 55,564 KB
testcase_23	AC	132 ms; 55,900 KB
testcase_24	AC	131 ms; 56,188 KB
testcase_25	AC	132 ms; 56,112 KB
testcase_26	AC	133 ms; 56,176 KB
testcase_27	AC	131 ms; 55,764 KB

ソースコード

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;

/**
 * Created by poly on 11/29/14.
 */
public class Main {
    static class GrahamScan {
        Stack<Point2D> hull = new Stack<Point2D>();

        // return extreme points on convex hull in counterclockwise order as an Iterable
        Iterable<Point2D> hull() {
            Stack<Point2D> s = new Stack<Point2D>();
            for (Point2D p : hull) s.push(p);
            return s;
        }

        GrahamScan(Point2D[] pts) {

// defensive copy
            int N = pts.length;
            Point2D[] points = new Point2D[N];
            for (int i = 0; i < N; i++)
                points[i] = pts[i];

// preprocess so that points[0] has lowest y-coordinate; break ties by x-coordinate
// points[0] is an extreme point of the convex hull
// (alternatively, could do easily in linear time)
            Arrays.sort(points);

// sort by polar angle with respect to base point points[0],
// breaking ties by distance to points[0]
            Arrays.sort(points, 1, N, points[0].POLAR_ORDER);

            hull.push(points[0]); // p[0] is first extreme point

// find index k1 of first point not equal to points[0]
            int k1;
            for (k1 = 1; k1 < N; k1++)
                if (!points[0].equals(points[k1])) break;
            if (k1 == N) return; // all points equal

// find index k2 of first point not collinear with points[0] and points[k1]
            int k2;
            for (k2 = k1 + 1; k2 < N; k2++)
                if (Point2D.ccw(points[0], points[k1], points[k2]) != 0) break;
            hull.push(points[k2 - 1]); // points[k2-1] is second extreme point

// Graham scan; note that points[N-1] is extreme point different from points[0]
            for (int i = k2; i < N; i++) {
                Point2D top = hull.pop();
                while (Point2D.ccw(hull.peek(), top, points[i]) <= 0) {
                    top = hull.pop();
                }
                hull.push(top);
                hull.push(points[i]);
            }

            assert isConvex();
        }


        // check that boundary of hull is strictly convex
        private boolean isConvex() {
            int N = hull.size();
            if (N <= 2) return true;

            Point2D[] points = new Point2D[N];
            int n = 0;
            for (Point2D p : hull()) {
                points[n++] = p;
            }

            for (int i = 0; i < N; i++) {
                if (Point2D.ccw(points[i], points[(i + 1) % N], points[(i + 2) % N]) <= 0) {
                    return false;
                }
            }
            return true;
        }
    }

    final static class Point2D implements Comparable<Point2D> {

        public static final Comparator<Point2D> X_ORDER = new XOrder();

        public static final Comparator<Point2D> Y_ORDER = new YOrder();

        public static final Comparator<Point2D> R_ORDER = new ROrder();

        public final Comparator<Point2D> POLAR_ORDER = new PolarOrder();

        public final Comparator<Point2D> ATAN2_ORDER = new Atan2Order();

        public final Comparator<Point2D> DISTANCE_TO_ORDER = new DistanceToOrder();

        private final double x; // x coordinate
        private final double y; // y coordinate

        public Point2D(double x, double y) {
            if (x == 0.0) x = 0.0; // convert -0.0 to +0.0
            if (y == 0.0) y = 0.0; // convert -0.0 to +0.0
            this.x = x;
            this.y = y;
        }

        public double x() {
            return x;
        }

        public double y() {
            return y;
        }

        public double r() {
            return Math.sqrt(x * x + y * y);
        }

        public double theta() {
            return Math.atan2(y, x);
        }

        private double angleTo(Point2D that) {
            double dx = that.x - this.x;
            double dy = that.y - this.y;
            return Math.atan2(dy, dx);
        }

        public static int ccw(Point2D a, Point2D b, Point2D c) {
            double area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
            if (area2 < 0) return -1;
            else if (area2 > 0) return +1;
            else return 0;
        }

        public static double area2(Point2D a, Point2D b, Point2D c) {
            return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
        }

        public double distanceTo(Point2D that) {
            double dx = this.x - that.x;
            double dy = this.y - that.y;
            return Math.sqrt(dx * dx + dy * dy);
        }

        public double distanceSquaredTo(Point2D that) {
            double dx = this.x - that.x;
            double dy = this.y - that.y;
            return dx * dx + dy * dy;
        }

        public int compareTo(Point2D that) {
            if (this.y < that.y) return -1;
            if (this.y > that.y) return +1;
            if (this.x < that.x) return -1;
            if (this.x > that.x) return +1;
            return 0;
        }

        // compare points according to their x-coordinate
        private static class XOrder implements Comparator<Point2D> {
            public int compare(Point2D p, Point2D q) {
                if (p.x < q.x) return -1;
                if (p.x > q.x) return +1;
                return 0;
            }
        }

        // compare points according to their y-coordinate
        private static class YOrder implements Comparator<Point2D> {
            public int compare(Point2D p, Point2D q) {
                if (p.y < q.y) return -1;
                if (p.y > q.y) return +1;
                return 0;
            }
        }

        // compare points according to their polar radius
        private static class ROrder implements Comparator<Point2D> {
            public int compare(Point2D p, Point2D q) {
                double delta = (p.x * p.x + p.y * p.y) - (q.x * q.x + q.y * q.y);
                if (delta < 0) return -1;
                if (delta > 0) return +1;
                return 0;
            }
        }

        // compare other points relative to atan2 angle (bewteen -pi/2 and pi/2) they make with this Point
        private class Atan2Order implements Comparator<Point2D> {
            public int compare(Point2D q1, Point2D q2) {
                double angle1 = angleTo(q1);
                double angle2 = angleTo(q2);
                if (angle1 < angle2) return -1;
                else if (angle1 > angle2) return +1;
                else return 0;
            }
        }

        private class PolarOrder implements Comparator<Point2D> {
            public int compare(Point2D q1, Point2D q2) {
                double dx1 = q1.x - x;
                double dy1 = q1.y - y;
                double dx2 = q2.x - x;
                double dy2 = q2.y - y;

                if (dy1 >= 0 && dy2 < 0) return -1; // q1 above; q2 below
                else if (dy2 >= 0 && dy1 < 0) return +1; // q1 below; q2 above
                else if (dy1 == 0 && dy2 == 0) { // 3-collinear and horizontal
                    if (dx1 >= 0 && dx2 < 0) return -1;
                    else if (dx2 >= 0 && dx1 < 0) return +1;
                    else return 0;
                } else return -ccw(Point2D.this, q1, q2); // both above or below

// Note: ccw() recomputes dx1, dy1, dx2, and dy2
            }

            int distCompare(Point2D p, Point2D q) {
                double dist1 = distanceSquaredTo(p);
                double dist2 = distanceSquaredTo(q);
                if (dist1 < dist2) return -1;
                else if (dist1 > dist2) return +1;
                else return 0;
            }
        }

        private class DistanceToOrder implements Comparator<Point2D> {
            public int compare(Point2D p, Point2D q) {
                double dist1 = distanceSquaredTo(p);
                double dist2 = distanceSquaredTo(q);
                if (dist1 < dist2) return -1;
                else if (dist1 > dist2) return +1;
                else return 0;
            }
        }

        public boolean equals(Object other) {
            if (other == this) return true;
            if (other == null) return false;
            if (other.getClass() != this.getClass()) return false;
            Point2D that = (Point2D) other;
            return this.x == that.x && this.y == that.y;
        }

        public String toString() {
            return "(" + x + ", " + y + ")";
        }

        public int hashCode() {
            int hashX = ((Double) x).hashCode();
            int hashY = ((Double) y).hashCode();
            return 31 * hashX + hashY;
        }
    }

    public static void main(String[] argv) {
        Scanner scanner = new Scanner(System.in);
        Point2D[] ps = new Point2D[5];
        for (int i = 0; i < 5; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            Point2D p = new Point2D(x, y);
            ps[i] = p;
        }
        GrahamScan g = new GrahamScan(ps);
        Iterable<Point2D> hull = g.hull();
        int count = 0;
        for (Point2D p : hull) {
            count++;
        }
        if (count == 5) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}