Parallel Lines

8839: Parallel Lines

时间限制: 10 Sec  内存限制: 128 MB
提交: 126  解决: 24
[提交] [状态] [讨论版] [命题人:admin]

题目描述

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, L3), (L1, L4), (L2, L3), (L2, L4) and (L3, L4) are parallel. So the maximum number of parallel line pairs, in this case, is 6.

 

输入

The input consists of a single test case of the following format.
m
x1 y1
.
.
.
xm ym

Figure B.2. Maximizing the number of parallel line pairs for Sample Input 2
The first line contains an even integer m, which is the number of points (2 ≤ m ≤ 16). Each of the following m lines gives the coordinates of a point. Integers xi and yi (−1000 ≤ xi ≤ 1000,−1000 ≤ yi ≤ 1000) in the i-th line of them give the x- and y-coordinates, respectively, of the i-th point.
The positions of points are all different, that is, xi ≠ xj or yi ≠ yj holds for all i ≠ j. Furthermore, No three points lie on a single line.

 

输出

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

 

样例输入

4
0 0
1 1
0 2
2 4

 

样例输出

1

 

 

一开始想的方式有些过于暴力。。超时

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
struct point
{
    int x,y;
}P[20];
bool vis[50];
double k[50];
int m,ans;
void dfs(int t)
{
    if(t>=m/2)
    {
        int cnt = 0;
        for(int i=0;i<m/2;i++)
            for(int j=i+1;j<m/2;j++)
                if(fabs(k[i]-k[j])<1e-6)
                    cnt++;
        ans = max(ans,cnt);
    }
    for(int i=0;i<m;i++)
    {
        for(int j=i+1;j<m;j++)
        {
            if(vis[i]||vis[j])
                continue;
            vis[i] = vis[j] = 1;
            k[t] = (double)(P[i].y-P[j].y)/(P[i].x-P[j].x);
            dfs(t+1);
            vis[i] = vis[j] = 0;
        }
    }
}
 
int main()
{
    scanf("%d",&m);
 
    for(int i=0;i<m;i++)scanf("%d%d",&P[i].x,&P[i].y);
 
    dfs(0);
 
    printf("%d\n",ans);
 
 
    return 0;
}

 

然后比赛结束后，又出现double掉精度了，难受X_X，还好最后想到了，将斜率转化

为x2*y1==x1*y2

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct point
{
    int x,y;
}P[50];
bool vis[50];
int k1[50],k2[50];
int m,ans;
void dfs(int t,int cn)
{
    if(cn>=m/2)
    {
        int cnt = 0;
        for(int i=0;i<cn;i++)
            for(int j=i+1;j<cn;j++)
                if(k1[i]*k2[j]==k2[i]*k1[j])
                    cnt++;
        ans = max(ans,cnt);
        return;
    }
    if(vis[t])
        dfs(t+1,cn);
    else
        for(int i=0;i<m;i++)
        {
            if(vis[i]||t==i)
                continue;
            k1[cn] = (P[i].y-P[t].y);
            k2[cn] = (P[i].x-P[t].x);
            vis[i] = vis[t] = 1;
            dfs(t+1,cn+1);
            vis[i] = vis[t] = 0;
        }
}

int main()
{
    scanf("%d",&m);

    for(int i=0;i<m;i++)scanf("%d%d",&P[i].x,&P[i].y);

    dfs(0,0);

    printf("%d\n",ans);

    return 0;
}
/*
8
0 0
0 5
2 2
2 7
3 -2
4 -2
5 0
8 2
*/