Aizu - 1379 —Parallel Lines (dfs)

Given an even number of distinct planar points, consider coupling all of the points into pairs. All the possible couplings are to be considered as long as all the given points are coupled to one and only one other point.

When lines are drawn connecting the two points of all the coupled point pairs, some of the drawn lines can be parallel to some others. Your task is to find the maximum number of parallel line pairs considering all the possible couplings of the points.

For the case given in the first sample input with four points, there are three patterns of point couplings as shown in Figure B.1. The numbers of parallel line pairs are 0, 0, and 1, from the left. So the maximum is 1.

Figure B.1. All three possible couplings for Sample Input 1

For the case given in the second sample input with eight points, the points can be coupled as shown in Figure B.2. With such a point pairing, all four lines are parallel to one another. In other words, the six line pairs (L1,L2)(L1,L2), (L1,L3)(L1,L3), (L1,L4)(L1,L4), (L2,L3)(L2,L3), (L2,L4)(L2,L4) and (L3,L4)(L3,L4) are parallel. So the maximum number of parallel line pairs, in this case, is 6.

Input

The input consists of a single test case of the following format.

mm
x1x1 y1y1
...
xmxm ymym

Figure B.2. Maximizing the number of parallel line pairs for Sample Input 2

The first line contains an even integer mm, which is the number of points (2≤m≤162≤m≤16). Each of the following mm lines gives the coordinates of a point. Integers xixi and yiyi (−1000≤xi≤1000,−1000≤yi≤1000−1000≤xi≤1000,−1000≤yi≤1000) in the ii-th line of them give the xx- and yy-coordinates, respectively, of the ii-th point.

The positions of points are all different, that is, xi≠xjxi≠xj or yi≠yjyi≠yj holds for all i≠ji≠j. Furthermore, No three points lie on a single line.

Output

Output the maximum possible number of parallel line pairs stated above, in one line.

Sample Input 1

4
0 0
1 1
0 2
2 4

Sample Output 1

1

Sample Input 2

8
0 0
0 5
2 2
2 7
3 -2
5 0
4 -2
8 2

Sample Output 2

6

Sample Input 3

6
0 0
0 5
3 -2
3 5
5 0
5 7

Sample Output 3

3

Sample Input 4

2
-1000 1000
1000 -1000

Sample Output 4

0

Sample Input 5

16
327 449
-509 761
-553 515
360 948
147 877
-694 468
241 320
463 -753
-206 -991
473 -738
-156 -916
-215 54
-112 -476
-452 780
-18 -335
-146 77

Sample Output 5

12

题意：

坐标轴中，给出点，任意两点相连，不会有奇数个，问互相平行的线最多有多少。

思路：

之前想的是求出任意两点的k的大小，然后判断相同k的个数最多的情况加上直线垂直情况的个数，就是答案了，但是这样想存在缺陷，因为，未必k相同最多就是最佳答案，可能存在多组不同k的最佳情况。

所以这个题因为数据量很小，所以dfs暴力枚举所有情况即可。

详见代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point
{
    int x,y;
}point[18];//存点
struct Vector
{
    int a,b;
}vec[10];//存向量
bool vis[18];//标记是否访问
int n,maxn,cnt;
void judge()//判断平行线的对数
{
    int ans = 0;
    for(int i = 0;i < cnt;i++)
        for(int j = i+1; j < cnt; j++)
            if(vec[i].a*vec[j].b == vec[i].b*vec[j].a)//向量平行判定
                ans++;
     maxn = max(maxn,ans);
        return ;
}
void dfs(int index)//点的下标从0开始
{
    while(vis[index])
       index++;//寻找未访问的点，减少dfs层数，这个必不可少
     if(index >= n)
     {
         judge();
         return;
     }
     vis[index] = 1; //标记访问
     for(int i = 0;i < n;i++)
     {
         if(!vis[i]&&index != i)//寻找未访问过的点
         {
             vis[i]  = 1;
             int ty = point[i].y - point[index].y;//存向量
             int tx = point[i].x - point[index].x;
             vec[cnt].a = tx ;
             vec[cnt].b = ty;
             cnt++;
             dfs(index+1);
             cnt--;              //回溯
             vis[i] = 0;
         }
     }
     vis[index] = 0;  //每层dfs别忘了回溯。
     return ;
}
int main()
{
    cnt = 0;
    cin>>n;
    memset(vis,0,sizeof vis);
    for(int i=0; i<n; i++)
    {
        cin>>point[i].x>>point[i].y;
    }
    maxn = 0;
    dfs(0);
    cout<<maxn<<endl;
    return 0;
}