import java.util.Collection;
import java.util.Iterator;
import java.util.Objects;

// you were not asked to write this class
class Point {
    private final int x, y;

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

    public int quadrant() {
        if (x > 0 && y > 0) {
            return 1;
        } else if (x < 0 && y > 0) {
            return 2;
        } else if (x < 0 && y < 0) {
            return 3;
        } else if (x > 0 && y < 0) {
            return 4;
        } else {
            return 0;
        }
    }

    public double distanceTo(Point other) {
        return Math.hypot(this.x - other.x, this.y - other.y);
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Point other) {
            return this.x == other.x && this.y == other.y;
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

// question 1
class Question1 {
    public static void removeInQuadrant(Collection<Point> points, int quadrant) {
        Iterator<Point> iterator = points.iterator();

        while (iterator.hasNext()) {
            if (iterator.next().quadrant() == quadrant) {
                iterator.remove();
            }
        }
    }
}

// question 2
class Line implements Comparable<Line> {
    private final Point start, end;

    public Line(Point start, Point end) {
        this.start = start;
        this.end = end;
    }

    public double length() {
        return this.start.distanceTo(this.end);
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Line other) {
            return this.start.equals(other.start) && this.end.equals(other.end);
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return Objects.hash(start, end);
    }

    @Override
    public int compareTo(Line other) {
        return Double.compare(this.length(), other.length());
    }
}

/*
question 3
(a) 0, 0
(b) 1, 0
(c) 3, 2
(d) 2, 2
(e) 1, 1
 */

// question 4
class ArrayBoundedList<E> {
    private final E[] elements;
    private int size;

    @SuppressWarnings("unchecked")
    public ArrayBoundedList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("negative capacity");
        }

        elements = (E[]) new Object[capacity];
    }

    public void add(E element) {
        if (size == elements.length) {
            throw new IllegalStateException();
        } else {
            elements[size++] = element;
        }
    }

    public void add(int index, E element) {
        Objects.checkIndex(index, size + 1);

        if (size == elements.length) {
            throw new IllegalStateException();
        }

        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }

        elements[index] = element;
        size++;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");

        for (int i = 0; i < size; i++) {
            sb.append(elements[i]);

            if (i < size - 1) {
                sb.append(", ");
            }
        }

        return sb.append("]").toString();
    }

    public void rotateLeft() {
        if (size > 0) {
            E temp = elements[0];

            for (int i = 0; i < size - 1; i++) {
                elements[i] = elements[i + 1];
            }

            elements[size - 1] = temp;
        }
    }

    public void reverse() {
        for (int i = 0; i < size / 2; i++) {
            E temp = elements[i];
            elements[i] = elements[size - i - 1];
            elements[size - i - 1] = temp;
        }
    }
}

/*
question 5:
(a) 6-10
(b) 2-4, 7-9
(c) 1, 2, 6, 7
(d) 1-3, 6-8
 */

/*
question 6:
5
b
1
3
[a, c, b]
 */

/*
Question 7:
7, 3, 1, 2
 */

/*
Question 8:
(a) 6-10
(b) 2-4, 7-9
(c) 1, 2, 6, 7
(d) 1-3, 6-8
 */

/*
Question 9:

Iterable
   ^
   |
Collection
   ^
   |
SequencedCollection
   ^
   |
List
   ^
   |
ArrayList
 */

/*
Question 10:
(a) O(n log n)
(b) O(n^2)
(c) O(1)
 */

/*
Question 11:
(a) O(1)
(b) O(1)
(c) O(1)
(d) O(n)
(e) O(1)
(f) O(n)
(g) O(n)
(h) O(n)
(i) O(n)
 */

/*
question 12:
(a) O(n^2)
(b) [b, d, ccc]

Explanation for part (b):

Initially:
indexes:     0  1    2  3   4
list:    [aaaa, b, ccc, d, ee]

i = 0 (0 < 5):
Remove "aaaa" and don't put it back in. So:
indexes:  0    1  2   3
list:    [b, ccc, d, ee]

i = 1 (1 < 4):
Remove "ccc" and put it back in at the end of the list. So:
indexes:  0  1   2    3
list:    [b, d, ee, ccc]

i = 2 (2 < 4):
Remove "ee" and don't put it back in. So:
indexes:  0  1    2
list:    [b, d, ccc]

i = 3: the loop condition is no longer true, as size() is 3.
 */