题解 | #两条公路#

知识点:

1.枚举

思路:

通过枚举每一个点的俩条直线(1,-1),然后计数
最后在进行一个双重循环,选出最大的(还要进行判断俩条直线有没有交点)

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cfloat>
#include<set>
#include<unordered_map>
using namespace std;


void solve() {
    int n;cin >> n;
    vector<int> x(n), y(n);
    set<pair<int, int>> pos;
    for (int i = 0;i < n;i++)    cin >> x[i];
    for (int i = 0;i < n;i++)    cin >> y[i];

    unordered_map<int, int> lines1,lines2;
    for (int i = 0; i < n; i++)
    {
        pos.insert({ x[i],y[i] });
        lines1[x[i] + y[i]]++;     //斜率为-1
        lines2[y[i] - x[i]]++;    //斜率为1
    }

    int ans = -1;
    unordered_map<int, int>::iterator it1=lines1.begin(),end1=lines1.end(),it2=lines2.begin(),end2=lines2.end();
    while (it1 != end1) {
        it2 = lines2.begin();
        while (it2 != end2) {
            // 那一段长长的就是判断有没有交点
            ans = max(ans,(*it1).second + (*it2).second - 
                (
                
                    (((*it1).first + (*it2).first) % 2 == 0) && 
                    (((*it1).first - (*it2).first) % 2 == 0) && 
                    (pos.contains({ 
                        ((
                            (*it1).first - (*it2).first))/2,
                        ((
                            (*it1).first + (*it2).first))/2 
                        }))
                ?1:0)
                );

            it2++;
        }
        it1++;
    }
    cout << ans;

}


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