結果

問題 No.199 星を描こう
ユーザー thorikawathorikawa
提出日時 2015-04-29 00:08:28
言語 Java21
(openjdk 21)
結果
AC  
実行時間 135 ms / 2,000 ms
コード長 9,279 bytes
コンパイル時間 2,566 ms
コンパイル使用メモリ 84,052 KB
実行使用メモリ 54,600 KB
最終ジャッジ日時 2024-06-09 13:45:19
合計ジャッジ時間 6,826 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 117 ms
53,992 KB
testcase_01 AC 105 ms
53,072 KB
testcase_02 AC 119 ms
54,600 KB
testcase_03 AC 118 ms
54,048 KB
testcase_04 AC 117 ms
54,212 KB
testcase_05 AC 121 ms
54,220 KB
testcase_06 AC 110 ms
54,232 KB
testcase_07 AC 127 ms
54,064 KB
testcase_08 AC 120 ms
54,144 KB
testcase_09 AC 124 ms
53,784 KB
testcase_10 AC 120 ms
53,916 KB
testcase_11 AC 110 ms
52,988 KB
testcase_12 AC 108 ms
53,220 KB
testcase_13 AC 118 ms
53,924 KB
testcase_14 AC 107 ms
53,112 KB
testcase_15 AC 113 ms
53,860 KB
testcase_16 AC 104 ms
52,944 KB
testcase_17 AC 129 ms
54,596 KB
testcase_18 AC 123 ms
54,036 KB
testcase_19 AC 134 ms
54,120 KB
testcase_20 AC 135 ms
54,224 KB
testcase_21 AC 124 ms
54,348 KB
testcase_22 AC 122 ms
54,128 KB
testcase_23 AC 122 ms
53,828 KB
testcase_24 AC 113 ms
53,580 KB
testcase_25 AC 124 ms
54,572 KB
testcase_26 AC 130 ms
54,152 KB
testcase_27 AC 129 ms
54,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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");
        }
    }
}
0