// Liam Keliher, 2023
//
// Input format validator for problem "Convex Hull Extension" (convexhullextension)
//
// Checks bounds on individual values, and then checks that:
// - the n points are distinct
// - no 3 points are collinear
// - all n points lie on the convex hull
// - the points are in counterclockwise order
//
// NOTE: doesn't use floating-point values anywhere


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

public class ConvexValidate {
    static final String POSINT_REGEX = "^(0|[1-9][0-9]*)$";
    static final String INT_INT_REGEX = "^(-[1-9][0-9]*|0|[1-9][0-9]*) (-[1-9][0-9]*|0|[1-9][0-9]*)$";
    static final int MIN_N = 3;
    static final int MAX_N = 50;
    static final int MIN_COORD = -1_000;
    static final int MAX_COORD = 1_000;
    static final int ERROR_MISSING_FIRST_LINE = 1;
    static final int ERROR_FIRST_LINE_REGEX_MISMATCH = 2;
    static final int ERROR_N_OUTSIDE_BOUNDS = 3;
    static final int ERROR_MISSING_COORDINATE_LINE = 4;
    static final int ERROR_COORDINATE_LINE_REGEX_MISMATCH = 5;
    static final int ERROR_COORDINATE_LINE_BAD_TOKEN_COUNT = 6;
    static final int ERROR_COORDINATE_OUTSIDE_BOUNDS = 7;
    static final int ERROR_EXTRA_LINE_AFTER_INPUT = 8;
    static final int ERROR_POINTS_NOT_DISTINCT = 9;
    static final int ERROR_THREE_POINTS_COLLINEAR = 10;
    static final int ERROR_NOT_ALL_POINTS_ON_CONVEX_HULL = 11;
    static final int ERROR_POINTS_NOT_IN_COUNTERCLOCKWISE_ORDER = 12;

    static final int ERROR_FIRST_POINT_NOT_ON_CONVEX_HULL = 1001;
    static final int ERROR_MYSTERIOUS_EXCEPTION = 1002;

    static final int SUCCESS = 42;
    //--------------------------------------------------------------------
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            // Check the first line (contains n)
            String line = br.readLine();
            if (line == null || line.length() == 0) {
                System.err.println("Expected first line of input, but found either nothing or an empty string");
                System.exit(ERROR_MISSING_FIRST_LINE);
            } // if
            if (!line.matches(POSINT_REGEX)) {
                System.err.println("First line of input does not match POSINT regex");
                System.exit(ERROR_FIRST_LINE_REGEX_MISMATCH);
            } // if

            // Check the bounds on n
            int n = Integer.parseInt(line);
            if (n < MIN_N || n > MAX_N) {
                System.err.println("n is not in the correct range");
                System.exit(ERROR_N_OUTSIDE_BOUNDS);
            } // if

            int[][] xy = new int[n][2];

            for (int i = 0; i < n; i++) {
                line = br.readLine();
                if (line == null || line.length() == 0) {
                    System.err.println("Expected i-th (x,y) coordinates (i = " + i + ", 0-based indexing), but found either nothing or an empty string");
                    System.exit(ERROR_MISSING_COORDINATE_LINE);
                } // if
                if (!line.matches(INT_INT_REGEX)) {
                    System.err.println("Line containing i-th (x,y) coordinates (i = " + i + ", 0-based indexing) does not match INT_INT regex");
                    System.exit(ERROR_COORDINATE_LINE_REGEX_MISMATCH);
                } // if

                // Double-check that line contains 2 tokens (redundant, but might as well)
                String[] tokens = line.split(" ");
                if (tokens.length != 2) {
                    System.err.println("Line containing i-th (x,y) coordinates (i = " + i + ", 0-based indexing) does not consist of 2 tokens");
                    System.exit(ERROR_COORDINATE_LINE_BAD_TOKEN_COUNT);
                } // if

                int x = Integer.parseInt(tokens[0]);
                int y = Integer.parseInt(tokens[1]);
                if (x < MIN_COORD || x > MAX_COORD || y < MIN_COORD || y > MAX_COORD) {
                    System.err.println("One of i-th (x,y) coordinates (i = " + i + ", 0-based indexing) is not in the correct range");
                    System.exit(ERROR_COORDINATE_OUTSIDE_BOUNDS);
                } // if
                xy[i][0] = x;
                xy[i][1] = y;
            } // for i

            // Check for any extra lines after the input is finished
            line = br.readLine();
            if (line != null) {
                System.err.println("At least one extra line (may or may not be NL-terminated) present at end of file");
                System.exit(ERROR_EXTRA_LINE_AFTER_INPUT);
            } // if

            if (!allPointsDistinct(xy)) {
                System.err.println("The n points are not distinct");
                System.exit(ERROR_POINTS_NOT_DISTINCT);
            } // if

            if (threePointsCollinear(xy)) {
                System.err.println("There are 3 collinear points");
                System.exit(ERROR_THREE_POINTS_COLLINEAR);
            } // if

            int[][] hull = convexHull(xy);

            if (hull.length != n) {
                System.err.println("Not all n points lie on the convex hull");
                System.exit(ERROR_NOT_ALL_POINTS_ON_CONVEX_HULL);
            } // if

            // Check that the n points are in counterclockwise order
            // - start by finding the position of the first input point on the convex hull
            int startIndex = -1;
            for (int i = 0; i < n; i++) {
                if (xy[0][0] == hull[i][0] && xy[0][1] == hull[i][1]) {
                    startIndex = i;
                    break;
                } // if
            } // for i

            if (startIndex == -1) {   // this should never happen, but check for it anyway
                System.err.println("First input point not found on the convex hull");
                System.exit(ERROR_FIRST_POINT_NOT_ON_CONVEX_HULL);
            } // if

            for (int i = 0; i < n; i++) {
                if (xy[i][0] != hull[(startIndex + i) % n][0] || xy[i][1] != hull[(startIndex + i) % n][1]) {
                    System.err.println("Points not in counterclockwise order");
                    System.exit(ERROR_POINTS_NOT_IN_COUNTERCLOCKWISE_ORDER);
                } // if
            } // for i
        } // try
        catch(Exception e) {
            System.err.println("A mysterious exception occurred");
            System.exit(ERROR_MYSTERIOUS_EXCEPTION);
        } // catch

        System.exit(SUCCESS);
    } // main(String[])
    //--------------------------------------------------------------------
    private static boolean allPointsDistinct(int[][] points) {
        int n = points.length;
        Set<String> pointSet = new HashSet<>(2*n);
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            String str = x + "," + y;
            if (pointSet.contains(str)) {
                return false;
            } // if
            else {
                pointSet.add(str);
            } // else
        } // for i
        return true;
    } // allPointsDistinct(int[][])
    //--------------------------------------------------------------------
    // Assumption: the n points are distinct
    // Basic idea:  For each pair of points, (x1,y1), (x2,y2), compute
    // the slope (rise/run) and the y-intercept of the line through them.
    // If another pair yields the same slope and y-intercept, then there
    // are 3+ collinear points.  In order for this to work, make sure
    // the 4-tuple (rise, run, yInterceptNumer, yInterceptDenom) has a
    // unique representation.
    // - store the slope as a reduced fraction with a positive denominator
    // - store the y-intercept as a reduced fraction with a positive denominator
    // - Special case:  if (x1,y1) and (x2,y2) are vertically aligned (x1 == x2),
    //   use slope 1/0, and use the x-intercept (x1/1 = x2/1) as the "y-intercept"
    //
    // NOTE:  complexity is O(n^2)
    // - since this problem is 3SUM hard, finding a sub-quadratric algorithm is probably not easy:
    // https://stackoverflow.com/questions/2734301/given-a-set-of-points-find-if-any-of-the-three-points-are-collinear

    private static boolean threePointsCollinear(int[][] points) {
        int n = points.length;
        Set<String> riseRunIntercept = new HashSet<>(n*n);   // > 2*(n choose 2)
        for (int i = 0; i < (n-1); i++) {
            int x1 = points[i][0];
            int y1 = points[i][1];
            for (int j = i + 1; j < n; j++) {
                int x2 = points[j][0];
                int y2 = points[j][1];
                int[] arr = getSlopeInterceptForm(x1, y1, x2, y2);
                String str = arr[0] + "," + arr[1] + "," + arr[2] + "," + arr[3];
                if (riseRunIntercept.contains(str)) {
                    return true;
                } // if
                else {
                    riseRunIntercept.add(str);
                } // else
            } // for j
        } // for i
        return false;
    } // threePointsCollinear(int[][])
    //--------------------------------------------------------------------
    // Returns a length-4 array representing the line through (x1,y2) and (x2,y2)
    // in slope-intercept form.  The slope is a fraction, rise/run, in reduced form,
    // with the convention that the denominator is never negative.  A vertical slope
    // is assigned the slope 1/0 (never -1/0).  The y-intercept is also a fraction
    // in reduced form, also with the convention that the denominator is positive.
    // For a vertical line with x-intercept x, the "y-intercept" is x/1 == x2/1.
    private static int[] getSlopeInterceptForm(int x1, int y1, int x2, int y2) {
        int rise = y2 - y1;
        int run = x2 - x1;

        int[] result = null;
        if (run == 0) {   // special case: x1 == x2
            result = new int[]{1, 0, x1, 1};
        } // if
        else {
            if (run < 0) {   // convention:  run should always be positive
                rise = -rise;
                run = -run;
            } // if
            int g = gcd(Math.abs(rise), run);
            rise /= g;
            run /= g;
            int yInterceptNumer = run*y1 - rise*x1;
            int yInterceptDenom = run;   // already positive
            g = gcd(Math.abs(yInterceptNumer), yInterceptDenom);
            yInterceptNumer /= g;
            yInterceptDenom /= g;
            result = new int[]{rise, run, yInterceptNumer, yInterceptDenom};
        } // else
        return result;
    } // getSlopeInterceptForm(int,int,int,int)
    //--------------------------------------------------------------------
    // Computes the convex hull of the n input points using the Graham scan.
    // Returns a 2-D array of points on convex hull in counterclockwise order
    // (size Hx2, where H is the number of points on the hull).
    // First finds the anchor point, which here is the point with the lowest
    // x-coord (in the case of a tie, choose the one with the lowest y-coord).
    //    Assumption #1:  n >= 3
    //    Assumption #2:  all n points are distinct
    //    Assumption #3:  no 3 points are collinear
    private static int[][] convexHull(int[][] points) {
        int n = points.length;
        int xMin = Integer.MAX_VALUE;
        int anchorPointIndex = -1; 
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            if (x < xMin) {
                xMin = x;
                anchorPointIndex = i;
            } // if
            else if (x == xMin) {
                int y = points[i][1];
                if (y < points[anchorPointIndex][1]) {   // found a lower leftmost point
                    anchorPointIndex = i;
                } // if
            } // else if
        } // for i

        int anchorX = points[anchorPointIndex][0];
        int anchorY = points[anchorPointIndex][1];

        // sortedPoints[] has length n-1 (since we are sorting the non-anchor points)
        PointSlope[] sortedPoints = new PointSlope[n-1];
        int spIndex = 0;
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            if (x != anchorX || y != anchorY) {
                sortedPoints[spIndex] = new PointSlope(x, y, y - anchorY, x - anchorX);
                spIndex++;
            } // if
        } // for i

        Arrays.sort(sortedPoints);

        int[][] stack = new int[n][2];

        // Push the anchor point and the first two sorted points onto
        // the stack (these will never form a right turn)
        // - first sorted point is always on the hull
        stack[0][0] = anchorX;
        stack[0][1] = anchorY;
        stack[1][0] = sortedPoints[0].x;
        stack[1][1] = sortedPoints[0].y;
        stack[2][0] = sortedPoints[1].x;
        stack[2][1] = sortedPoints[1].y;
        int stackSize = 3;

        for (spIndex = 2; spIndex < (n-1); spIndex++) {
            // Push next sorted point onto the stack (might get popped off later)
            stack[stackSize][0] = sortedPoints[spIndex].x;
            stack[stackSize][1] = sortedPoints[spIndex].y;
            stackSize++;
            while (rightTurn(stack[stackSize-3], stack[stackSize-2], stack[stackSize-1])) {
                // Remove the second-from-the-top stack entry
                stack[stackSize-2][0] = stack[stackSize-1][0];
                stack[stackSize-2][1] = stack[stackSize-1][1];
                stackSize--;
            } // while
        } // for spIndex

        return Arrays.copyOf(stack, stackSize);
    } // convexHull(int[][])
    //--------------------------------------------------------------------
    // Determine if travelling from p1 to p2 to p3 involves a right turn
    // by checking if p2 lies to the left of the line through p1 and p3
    // (where "left" is relative to the orientation when travelling from
    // p1 to p3).  If the line is not vertical or horizontal (special cases),
    // check this by plugging (x2,y2) into y = mx + b.
    private static boolean rightTurn(int[] p1, int[] p2, int[] p3) {
        int x1 = p1[0];
        int y1 = p1[1];
        int x2 = p2[0];
        int y2 = p2[1];
        int x3 = p3[0];
        int y3 = p3[1];
        int[] arr = getSlopeInterceptForm(x1, y1, x3, y3);
        int rise = arr[0];
        int run = arr[1];
        int yInterceptNumer = arr[2];
        int yInterceptDenom = arr[3];
        if (run == 0) {   // x1 == x3 (vertical line)
            if ((y1 < y3 && x2 < x1) || (y1 > y3) && x2 > x1) {
                return true;
            } // if
        } // if
        else {   // line is not vertical
            // Compare y2 to m*x2 + b
            // *** avoid int overflow ***
            long numer = (long)rise*x2*yInterceptDenom  + (long)run*yInterceptNumer;
            long denom = (long)run*yInterceptDenom;
            if (x1 < x3 && y2*denom > numer) {
                return true;
            } // if
            else if (x1 > x3 && y2*denom < numer) {
                return true;
            } // else if
        } // else
        return false;
    } // rightTurn(int[],int[],int[])
    //--------------------------------------------------------------------
    private static int gcd(int a, int b) {
        while (b != 0) {
            int rem = a % b;
            a = b;
            b = rem;
        } // while
        return a;
    } // gcd(int,int)
    //--------------------------------------------------------------------
} // class ConvexValidate

//#######################################################################

// An instance of this class holds a point (x,y) along with the slope of
// the line through (x,y) and the anchor point (the anchor point itself
// is not stored in a PointSlope object).  The slope is represented as
// the fraction rise/run (not necessarily in reduced form, but always
// with a non-negative denominator).
// NOTE: For the program above, at most one point can have vertical
//       slope, i.e, run = 0, which is the "largest" slope.

class PointSlope implements Comparable<PointSlope> {
    int x;
    int y;
    int rise;
    int run;

    PointSlope(int inX, int inY, int inRise, int inRun) {
        x = inX;
        y = inY;
        rise = inRise;
        run = inRun;
        if (run < 0) {
            rise = -rise;
            run = -run;
        } // if
    } // constructor PointSlope(int,int,int,int)

    @Override
    public int compareTo(PointSlope other) {
        if (this.run == 0) {   // "largest" slope
            return 1;
        } // if
        else if (other.run == 0) {
            return -1;
        } // else if

        // No danger of int overflow, since each coord is in [-1_000, 1_000]
        if (this.rise*other.run - other.rise*this.run < 0) {
            return -1;
        } // if
        else {   // > 0 case, since == 0 can't happen when all points are distinct and no 3 are collinear
            return 1;
        } // else
    } // compareTo(PointSlope)
} // class PointSlope