Questions
=========================================

Minimum Area Rectangle
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: none

    Given a set of distinct points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.
    If there isn't any rectangle, return 0.
    Example 1:
    Input: [[1,1],[1,3],[3,1],[3,3],[2,2]], Output: 4
    Example 2:
    Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]], Output: 2

----

In this question, the sides of the rectangle must be parallel to the main axis, so we don't have to consider a rotated rectangle. If we know the coordinates of the two diagonal vertices of the rectangle, it is very simple to find the area!

So we just need to find all the pair of points where their abscissa and ordinate are different.

In order to optimize the search time, the ordinates of all points with the same abscissa can be put into a HashSet in advance,

.. only:: html

    - https://leetcode.com/problems/minimum-area-rectangle/


Relative Location
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: none

    Given a string of two point names and coordinate position relationship, return whether there is such a position relationship (that is, whether there is a contradiction). The relationship could be one of: N, S, W, E, NE, NW, SE, SW.

    Example:
    Input: "1 NE 2, 2 SE 3, 3 W 1"
    Output: true
    Explanation:

    3       1

        2

    point 1 is in the northeast of point 2, and point 2 is southeast of 3, point 3 is at the west side of point 1. It is spatially reasonable.

.. only:: html

    - https://www.1point3acres.com/bbs/thread-876745-1-1.html

----

This is basically a graph problem.

.. literalinclude:: code/relative_location_test.cpp
    :language: c++
    :linenos:


Edit Distance
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: none

    Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
    You have the following three operations permitted on a word:
        Insert a character
        Delete a character
        Replace a character

    Example 1:
    Input: word1 = "horse", word2 = "ros"
    Output: 3
    Explanation:
    horse -> rorse (replace 'h' with 'r')
    rorse -> rose (remove 'r')
    rose -> ros (remove 'e')

    Example 2:
    Input: word1 = "intention", word2 = "execution"
    Output: 5
    Explanation:
    intention -> inention (remove 't')
    inention -> enention (replace 'i' with 'e')
    enention -> exention (replace 'n' with 'x')
    exention -> exection (replace 'n' with 'c')
    exection -> execution (insert 'u')

.. only:: html

    - https://leetcode.com/problems/edit-distance/

Fix Sentence
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: none

    Given a sentence string and a dictionary. There are wrong words in the sentence while the correct words are in the dictionary. Can you correct the sentence with the dictionary with reasonable assumption?

    Example
    Input: Todxy is a god day.
    Dictionary: {today, good}
    Output: Today is a good day.

.. only:: html

    - https://www.1point3acres.com/bbs/thread-876745-1-1.html

Max Points on a Line
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: none

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

    Example 1:
    Input: [[1,1],[2,2],[3,3]]
    Output: 3
    Explanation:
    ^
    |
    |        o
    |     o
    |  o
    +------------->
    0  1  2  3  4
    
    Example 2:
    Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
    Output: 4
    Explanation:
    ^
    |
    |  o
    |     o        o
    |        o
    |  o        o
    +------------------->
    0  1  2  3  4  5  6

-----

According to junior high school mathematics, it can be known that two points determine a straight line, and it can be written in the form of y = ax + b. All collinear points satisfy this formula. Therefore, a slope can be calculated between each pair of these given points. Each slope represents a straight line. For each straight line, bring in all the points to see if they are collinear and calculate the number. This is the basic idea.

However, there are two special cases to be considered. One is that when two points are duplicates, a straight line cannot be formed. The second is the case where the slope does not exist where their x coordinates are the same.

.. image:: max_points.png


.. literalinclude:: code/149_Max_Points_on_a_Line.h
    :language: c++
    :linenos:
    :lines: 14-39

.. only:: html

    https://leetcode.com/problems/max-points-on-a-line/


|:alien:| If we want to use drone for delivery, what can be done with ML?


Detect Squares
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: none

    You are given a stream of points on the X-Y plane. Design an algorithm that:

    Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points.
    Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the query point form an axis-aligned square with positive area.
    An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis.

    Implement the DetectSquares class:

     - DetectSquares() Initializes the object with an empty data structure.
     - void add(int[] point) Adds a new point point = [x, y] to the data structure.
     - int count(int[] point) Counts the number of ways to form axis-aligned squares with point point = [x, y] as described above.

----

.. literalinclude:: code/detect_square_test.cpp
    :language: c++
    :linenos:


.. only:: html

    - https://leetcode.com/problems/detect-squares/
    - https://www.youtube.com/watch?v=bahebearrDc&ab_channel=NeetCode