题解 | #最佳射击#

知识点:

1.数学
2.枚举

思路:

1.先求所有的直线
	任意选择两个点建立一条直线
	并判断有多少个点在直线上
2.我们需要任选俩条直线(上面求的)
	先选第一条,更新答案,可能是孤立点+直线或者只有一条直线
	判断俩直线有没有垂直(可以是旋转的一组)与相交(应该减去交点)

注意点: 1.当n<=2特殊处理 2.重复点的去除,不能break 3.当只有一条直线的时候:孤立点加一条直线

代码实现:

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cfloat>
#include<set>
#include<unordered_map>

using namespace std;


struct line
{
    long long x1, y1, x2, y2;
    int cnt;
    line(long long x1, long long y1, long long x2, long long y2,int n) {
        this->x1 = x1;
        this->x2 = x2;
        this->y1 = y1;
        this->y2 = y2;
        cnt = n;
    }
};


bool check(line &l,long long x3, long long y3) {
    return (l.x2 - l.x1)* (y3 - l.y1) == (l.y2-l.y1)*(x3-l.x1);
}

void solve() {
    int n,a,b;cin >> n;
    vector<long long> x(n), y(n);

    for (int i = 0;i < n;i++)    cin >> x[i];
    for (int i = 0;i < n;i++)    cin >> y[i];
    //	1.当n<=2特殊处理
    if (n <= 2) {
        cout << n;
        return;
    }

    vector<line> lines;
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1;j < n;j++) {
            //任选俩点构成一条直线
            if (x[i] == x[j] && y[i] == y[j]) continue;
            //判断有多少点在这条直线上
            int cnt = 0;
            for (int k = 0; k < n; k++)
                if ((y[k] - y[i]) * (x[j] - x[i]) == (y[j] - y[i]) * (x[k] - x[i]))
                    cnt++;

            //加入我们的lines,可能会一条同一条线多次算但是不影响结果
            lines.push_back(line(x[i], y[i], x[j], y[j], cnt));
        }
    }

    //先任选一条线，记录点个数，然后再选看能不能选出垂直的新线
    int ans = 0, sz = lines.size();
    
    for (int i = 0; i < sz; i++)
    {
        // 3.当只有一条直线的时候:孤立点加一条直线
        ans = max(ans, min(n,lines[i].cnt+1));
        for (int j = i+1; j < sz; j++)
        {
            //往后选出lines[i]与lines[j]线,判断是不是垂直
            line& l1 = lines[i],&l2=lines[j];
            
            //垂直
            if ((l1.x2 - l1.x1) * (l2.x2 - l2.x1) == -(l1.y2 - l1.y1) * (l2.y2 - l2.y1)) {
                
                int sub = 0;
                for (int k = 0; k < n; k++)
                {
                    //遍历点,如果一个点同时在l1与l2,sub=1
                    if (check(l1, x[k], y[k]) && check(l2, x[k], y[k])) {
                        //2.重复点的去除,不能break
                        sub = 1;
                    }
                }
                ans = max(ans, lines[i].cnt + lines[j].cnt - sub);
            }
        }
    }
    cout << ans;

}


int main() {
    std::ios::sync_with_stdio(false); std::cin.tie(0);
    solve();
    return 0;
}