Parallel Lines Aizu – 1379

DFS暴力枚举线段组成情况。。。

#include <bits/stdc++.h>
#define ms(x) memset(x, 0, sizeof(x))
using namespace std;
const int N = 20;
struct node{
    int x, y;
}q[N];
int vis[N], n, top, ans = 0;
vector<pair<int, int> >que;
bool check(){
    int tp = 0;
    for(int i=0;i<que.size();i++){
        int dx = q[que[i].first].x - q[que[i].second].x;
        int dy = q[que[i].first].y - q[que[i].second].y;
        for(int j=0;j<que.size();j++){
            if(i==j) continue;
            int tx = q[que[j].first].x - q[que[j].second].x;
            int ty = q[que[j].first].y - q[que[j].second].y;
            if(ty*dx == dy*tx) tp++;
        }
    }
    ans = max(tp, ans);
}
void dfs(int now){
    if(now == n+1){
        check();
        return ;
    }
    if(vis[now]) dfs(now+1);
    else{
        for(int i=1;i<=n;i++) {
            if(vis[i]||i==now) continue;
            que.push_back(make_pair(now, i));
            vis[i] = vis[now] = 1;
            dfs(now+1);
            que.pop_back();
            vis[now] = vis[i] = 0;
        }
    }
}
int main(){
    while(scanf("%d", &n)!=EOF){
        ms(vis);
        ans = 0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&q[i].x,&q[i].y);
        }
        dfs(1);
        printf("%d\n",ans/2);
    }
    return 0;
}

转载自：https://blog.csdn.net/khn64/article/details/81666610