需求：给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
分析思路：

1、将所有点二维坐标化，即定义出所有点的x，y坐标值

2、遍历出所有取出两点的情况(不考虑先后顺序)，根据任意两点都确定一条直线，直线参数为k斜率，b与y轴交点的纵坐标（此时x=0），将他们放入一个列表中

3、将所有直线放入一个集合并完成去重操作，增加直线的第三个参数n=0用于第四步判断每条直线上有几个点

4、将所有点遍历并判断是否在集合中的直线上，若在直线上，则直线对应的n加1

5、遍历所有代表直线的列表，取出n最大的直线其n值就是最多有n个点在此条直线上
def line(point1, point2):     
	#定义一个函数通过两点来计算出对应直线的参数，
	#传入的参数point1、point2都是列表
	try:
        y1 = point1[1]
        y2 = point2[1]
        x1 = point1[0]
        x2 = point2[0]
  	    #根据列表对应下标取出x、y值
        k = (y2-y1)/(x2-x1)
        #根据x、y值计算出斜率，当斜率无穷大时报错，进入except
        b = y1-k*x1
        #计算出b
        return [k, b,0]
        #返回直线参数，第三个参数为0，用来后面的计数
    except Exception:
        return ["+8", y1, 0]
        #当报错时意味着斜率为无穷大，我们用"+8"代替


def judge_in(point_in, line_in):
	#用来判断点是否在直线上，若在则返回True，
	#若不在则返回False
    x_in = point_in[0]
    y_in = point_in[1]
    k_in = line_in[0]
    b_in = line_in[1]
    if k_in == "+8":
    #当斜率无穷大时，单独判断
        if b_in == y_in:
            return True
        else:
            return False
    elif y_in == x_in*k_in+b_in:
        return True
    else:
        return False

"""可以改变下方列表中点的参数"""
point_list = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]
#给出一个包含几个点的列表


# point_list = [[1,1],[2,2],[3,3]]
line_list = []
#新建一个用来接收直线的空列表
new_list = []
#直线去重后加入此列表
for i in range(len(point_list)):
    for j in range(i+1, len(point_list)):
    #通过双层的for循环给出所有两个点的组合
        line_s = line(point_list[i], point_list[j])
        #利用函数求出直线的前两个参数
        line_list.append(line_s)

print(line_list)
#得到的是一组有重复参数的直线
for k in line_list:
    if k not in new_list:
    #去重
        new_list.append(k)
for m in point_list:
    for n in new_list:
    #遍历所有点和线，判断点是否在线上，
    #若在则直线第三个用来计数的参数加1
        if judge_in(m, n):
            n[2] += 1
print(new_list)
#输出去重完毕后的列表，再经过一次遍历即可找出最多点所在的直线

对应题目

UPC NO.78场 问题 E: 阅兵队形 plane

题目描述

70 周年阅兵的时候，飞机在空中排练着队形，Yyx 很好奇，他想知道这么训练有素的队形到底是如何造就的呢？他记录下了飞行路径上的各个端点。

他发现：把整个天空看做一个平面直角坐标系，飞行路径是所有过任意两个端点的直线。

如果这些飞机可能会撞在一起，或者说只要这些直线有交点，就可能发生事故。

在所有直线中应该最少删除多少条直线使得剩下的直线两两都不相互平行（重合也是平行）。

求出最多可以构成多少条两两互不平行的直线。
输入

第一行，整数 n。

接下来 n 行，每行两个整数 x,y，表示这个端点的横坐标与纵坐标。

输出

一行，一个整数 ans，表示答案。
样例输入

4

-1 1

-2 0

0 0

1 1

样例输出

4
提示

对于所有数据，2≤N≤200，-1000≤Xi≤1000，-1000≤Yi≤1000。

在所有直线中应该最少删除多少条直线使得剩下的直线两两都不相互平行。
题意：


在坐标纸上有N个不重合的点，两两可以连一个线段并延伸成直线，请问在这些直线里最多能选出多少条使得他们两两不平行也不重合（题目可能有点饶头，要求的就是题目描述的最后一行，它的上面一句和样例的提示纯属出自出题人的 “善意”… ）。

下面2种算法思路的直线都是通过n^2枚举出来的
思路1：


首先讲一种常见的思路：运用斜率＋特判来解决问题。

具体做法：

考虑斜率k

特判直线垂直于x轴的情况（k负一个特殊值）

用map进行判断

#include<bits/stdc++.h>
using namespace std;
int n,ans,x1[520],y1[520];
map<double,bool>f;

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)  cin>>x1[i]>>y1[i];
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
        {
            int lx = x1[i]-x1[j];
            int ly = y1[i]-y1[j];
            double k;
            if(lx==0)  k=5.25;
            else k = (double)ly/lx;
            if(!f[k]) {f[k]=1;    ans++;}
        }
    cout<<ans<<endl;
    return 0;
}

/*
另一写法：求出每两个点间的斜率，排序后判断
#include<bits/stdc++.h>
#define N 201
#define eps 1e-6
#define PI acos(-1.0)
using namespace std;
struct Point {double x, y;} p[N];
double a[N*N];
int n;

double FindSlewRate(Point p1, Point p2)
{
    Point p;
    p.x = p2.x-p1.x;
    p.y = p2.y-p1.y;
    if(abs(p.x)<eps)  return PI/2;     //斜率不存在
    double tmp = atan(p.y/p.x);
    if(tmp<0)  return PI+tmp;
    return tmp;
}
 
int cmp(const void *c, const void *d){
    return *(double *)c > *(double *)d ? 1:-1;
}

int main()
{
    while(~scanf("%d", &n))
    {
        for(int i=0; i<n; i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        
        int rt=0;
        for(int i=0; i<n; i++)
            for(int j=i+1; j<n; j++)
                a[rt++] = FindSlewRate(p[i], p[j]);
        
        qsort(a,rt,sizeof(a[0]),cmp);
        
        int ans=1;
        for(int i=1; i<rt; i++)
            if(a[i] != a[i-1])    ans++;
        
        printf("%d\n", ans);
    }
    return 0;
}
*/

思路2：


再介绍一种运用向量的做法：考虑使用向量进行判断两点是否平行

具体做法：

需要对向量进行特殊处理

1.首先让x不小于0

2.如果x==0那么y就取绝对值

3.x , y 除以 (x , y) 的绝对值的最大公因数

这样的话，每一种方向的向量就只有唯一的表示方法

用桶进行判断（注意y可能为负）

#include<bits/stdc++.h>
using namespace std;
int x[520],y[520];
bool flag[5200][5200];
int n,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)    cin>>x[i]>>y[i];
    
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            int lx=x[i]-x[j];
            int ly=y[i]-y[j];
            if(lx<0) 
            {
                lx = -lx;
                ly = -ly;
            }
            else if(lx==0)    ly=abs(ly);
            int gcd = __gcd(lx,abs(ly));
            lx /= gcd;
            ly /= gcd;
            if(!flag[lx][ly+2005])
            {
                ans++;
                flag[lx][ly+2005] = 1;
            }
        }
        
    cout<<ans<<endl;
    return 0;
}

计算直线的交点数
Problem Description
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。

比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
问题分析
将n条直线排成一个序列，直线2和直线1最多只有一个交点，直线3和直线1，2最多有两个交点,……，直线n 和其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数：
Max = 1 +2 +……+（n-1）=n(n-1)/2;
这些直线有多少种不同的交点数
 当n = 1， 2， 3时情况很容易分析。当n = 4 时，我们可以按如下分类方法，逐步计算。
 1. 四条直线全部平行，无交点。
 2. 其中三条平行，交点数: 3*(n-3)+0 = 3；
 3. 其中两条平行，而另外两条直线的交点既可能平行也可能相交，因此交点数据分别为：

   2*(n-2) + 0 = 4
   2*(n-2) + 1 = 5

4. 四条直线互不平行， 交点数为1*(n-1) + {3条直线的相交情况}：

   1*(n-1)+0=3 

   1*(n-1)+2=5 

   1*(n-1)+3=6

即n=4时，有0, 3, 4, 5, 6个不同的交点数.所以有5种可能。
从上述n=4的分析过程中，发现：
m条直线的交点数=r条平行线与m-r条直线交叉的交点数+ m-r条直线本身的交点数 =r*(m-r) + m-r条直线之间的交点数。(1<=r<=m)
{m条直线的交点数集合} = U {  r条平行线与m-r条直线交叉的交点数 + {m-r条直线本身的交点数集合}  } =  U {  r*(m-r) + {m-r条直线之间的交点数集合}  }。(1<=r<=m)
 注意：数和集合相加 = 数和集合中每个元素相加组成的新集合。
 如何编写程序？
 程序框架如下：
//Ui表示i条直线的交点数集合
初始化U0= {0}, U1= {0}
For n = 2 to N
   Un = {}                            //初始化Un
为空集
   For i = 1 to n       //i表示平行线个数
                   Un =Un  U  { i*(n-i) + Un-i}        //并运算
 注意：数和集合相加 = 数和集合中每个元素相加组成的新集合。
 用C++代码实现，我们可以用set集合，最简单的方法是用数组表示交点数集合。
二维数组 p[i][j] 表示i条直线，j个交点数是否存在。存在值为1，不存在值为0.
#include <stdio.h>

int main()

{

 int p[21][200], n; //200为交点数的上限，交点数为1+2+3+…(n-1)

 memset(p, 0, sizeof(p));

 for(int i=0; i<21; i++)

 p[i][0]=1; //不管多少直线都存在0个交点的情况，即所有直线平行

 for(int n=2; n<21; n++) //动态规划p[i][j]表示i条直线，交点数为j.当  p[i][j]=1,则表示i条直线中，存在交点数为j的情况

     for(int i=1; i < n; i++) //n条直线平行的情况已经考虑了，无需重复

          for(int j=0; j<200; j++)

              {

                 if(p[n-i][j]==1)

                    p[n][j+i*(n-i)]=1;  
              }
 while (scanf("%d", &n) != EOF)

 {

    for (j=0; j <= n*(n-1)/2; j++)   //n*(n-1)/2能形成的最大交点数

    {
     if (f[n][j])

             printf("%d ",j);

    }

     printf("\n");

 }

   return 0;
}
 
 
 
这个是转载别人的，感觉好强大，我一直在想：我怎么当我知道i(n-i)条直线平行时，我又怎么可以把n-i条剩余的直线的所有可能加上去呢。加上去后我怎么存储呢？
而这个程序他运用了逆向的思想，从头到尾做出了所有可能的表格 。要不然怎么叫做规划呢？而且还是动态的？
 
首先他用i行表示多少条线，用数组元素为1表示该元素的j为可能存在的交点个数。
然后从数组2行开始往后规划，规划的方法是：i条线平行。n-i条线得出行数存在的交点情况加上i(n-i)，然后在相应得到交点数赋值为1

计算直线的交点数
Problem Description
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。

比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
问题分析
将n条直线排成一个序列，直线2和直线1最多只有一个交点，直线3和直线1，2最多有两个交点,……，直线n 和其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数：
Max = 1 +2 +……+（n-1）=n(n-1)/2;
这些直线有多少种不同的交点数
当n = 1， 2， 3时情况很容易分析。当n = 4 时，我们可以按如下分类方法，逐步计算。
1. 四条直线全部平行，无交点。
2. 其中三条平行，交点数: 3*(n-3)+0 = 3；
3. 其中两条平行，而另外两条直线的交点既可能平行也可能相交，因此交点数据分别为：

   2*(n-2) + 0 = 4
   2*(n-2) + 1 = 5

4. 四条直线互不平行， 交点数为1*(n-1) + {3条直线的相交情况}：

   1*(n-1)+0=3


   1*(n-1)+2=5 

   1*(n-1)+3=6

即n=4时，有0, 3, 4, 5, 6个不同的交点数.所以有5种可能。
从上述n=4的分析过程中，发现：
m条直线的交点数=r条平行线与m-r条直线交叉的交点数+ m-r条直线本身的交点数 =r*(m-r) + m-r条直线之间的交点数。(1<=r<=m)
{m条直线的交点数集合} = U {  r条平行线与m-r条直线交叉的交点数 + {m-r条直线本身的交点数集合}  } =  U {  r*(m-r) + {m-r条直线之间的交点数集合}  }。(1<=r<=m)
如何编写程序？
程序框架如下：
//Ui表示i条直线的交点数集合
初始化U0= {0}, U1= {0}
For n = 2 to N
   Un = {}                            //初始化Un为空集
   For i = 1 to n       //i表示平行线个数
                   Un =Un U  { i*(n-i) + Un-i}        //并运算
注意：数和集合相加 = 数和集合中每个元素相加组成的新集合。
用C++代码实现，我们可以用set集合，最简单的方法是用数组表示交点数集合。
二维数组 p[i][j] 表示i条直线，j个交点数是否存在。存在值为1，不存在值为0.
#include <stdio.h>

int main()

{

int p[21][200], n; //200为交点数的上限，交点数为1+2+3+…(n-1)

memset(p, 0, sizeof(p));

for(int i=0; i<21; i++)

p[i][0]=1; //不管多少直线都存在0个交点的情况，即所有直线平行

for(int n=2; n<21; n++) //动态规划p[i][j]表示i条直线，交点数为j.当  p[i][j]=1,则表示i条直线中，存在交点数为j的情况

     for(int i=1; i < n; i++) //n条直线平行的情况已经考虑了，无需重复

          for(int j=0; j<200; j++)

              {

                 if(p[n-i][j]==1)

                    p[n][j+i*(n-i)]=1;  
              }
while (scanf("%d", &n) != EOF)

{

    for (j=0; j <= n*(n-1)/2; j++)   //n*(n-1)/2能形成的最大交点数

    {
     if (f[n][j])

             printf("%d ",j);

    }

     printf("\n");

}

   return 0;
}