Link: https://www.nowcoder.com/questionTerminal/d3f26db0325444078717cc802e0056d8 Source: NowCoder

Xiayi is playing a new shooting game that takes place on a two-dimensional plane. Xiayi is at the origin (0,0), and there are n monsters on the plane, each with coordinates (x[i], y[i]). With one shot, Xiayi can eliminate all monsters that are on the x-axis and y-axis (including the origin) at once. Xiayi is a VIP player in this game and has two special privilege operations:

1. Make all monsters on the plane move simultaneously in any same direction for any same distance
2. Make all monsters on the plane rotate around Xiayi (0,0) by any same angle simultaneously Xiayi wants to take a shot. Before shooting, he can use these two privilege operations any number of times.

Xiayi wants to know the maximum number of monsters he can eliminate at once when he shoots. Please help Xiayi.

As shown in the example:

All points can be rotated clockwise or counterclockwise by 45° with respect to the origin (0,0), which places all points on the coordinate axes, so all 5 monsters can be eliminated.

Input Description:

The input consists of three lines. The first line contains a positive integer n (1 ≤ n ≤ 50), representing the number of monsters on the plane. The second line includes n integers x[i] (-1,000,000 ≤ x[i] ≤ 1,000,000), representing the x-coordinate of each monster, separated by spaces. The third line includes n integers y[i] (-1,000,000 ≤ y[i] ≤ 1,000,000), representing the y-coordinate of each monster, separated by spaces.

Output Description:

Output an integer representing the maximum number of monsters Xiayi can eliminate.

Example 1

Input

5 0 -1 1 1 -1 0 -1 -1 1 1

Output

5

Analysis

The problem is equivalent to finding a cross shape that covers as many points as possible. Considering that one line can cover at least two points, and adding a perpendicular line can cover at least 3 points, we can iterate based on this. For any three points, we select two of them to form a line (three possible combinations), and for the third point, we create a perpendicular line to this line. This cross shape already passes through three points. For the remaining points, we check if they are on this cross shape. To determine if a point is on the cross shape, first check if it’s on the same line as the first line. Otherwise, determine if the line formed by this point and the third point is perpendicular to the second line. When there are three or fewer points, we can cover all of them.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct point{
    int x = 0;
    int y = 0;
};

bool is_sameline(point p1, point p2, point p3){
    return ((p1.x - p2.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p2.y)) == 0;
}

bool is_vertical(point p1, point p2){
    return (p1.x * p2.x + p1.y * p2.y) == 0;
}

bool is_vertical(point p1, point p2, point p3, point p4){
    point v1, v2;
    v1.x = p1.x - p2.x;
    v1.y = p1.y - p2.y;
    v2.x = p3.x - p4.x;
    v2.y = p3.y - p4.y;
    return is_vertical(v1, v2);
}

int main()
{
    int n, ret = 0;
    cin >> n;
    point inputs[n];
    for (int i = 0; i < n; i++)
        cin >> inputs[i].x;
    for (int i = 0; i < n; i++)
        cin >> inputs[i].y;
    if (n < 4)
    {
        cout << n << endl;
        return 0;
    };
    vector<int> select = {1, 1, 1};
    for (int i = 0; i < n - 3; i++)
        select.push_back(0);
    do
    {
        vector<point> shizi;
        for (int i = 0; i < n; i++)
        {
            if (select[i])
            {
                shizi.push_back(inputs[i]);
            }
        }
        vector<vector<point>> status;
        status.push_back({shizi[0], shizi[1], shizi[2]});
        status.push_back({shizi[0], shizi[2], shizi[1]});
        status.push_back({shizi[1], shizi[2], shizi[0]});
        for (auto points : status)
        {
            int count = 0;
            for (int i = 0; i < n; i++)
            {
                if (!select[i])
                {
                    if (is_sameline(points[0], points[1], inputs[i]))
                        count++;
                    if (is_vertical(points[0], points[1], points[2], inputs[i]))
                        count++;
                }
            }
            ret = max(ret, count);
    
        }
    } while (prev_permutation(select.begin(), select.end()));
    cout << ret + 3 << endl;
    return 0;
}