连线游戏【模拟】

题目大意：

给出n$n$个点，将它们两两连线，使得没有两条线互相平行。求最多能连几条线。

---

思路：

“使得没有两条线互相平行”其实就是说连的每条线的斜率都不一样，而斜率又很好求（斜率=(y1−y2)×(x1−x2)$=(y1-y2)\times (x1-x2)$），那么就将斜率排好序，判断相邻的两个是否相等（相等就代表两条线平行），记录答案即可。
时间复杂度：O(n2)$O(n^2)$

---

代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

int n,sum,k;
double x[501],y[501],a[1000001];

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        for (int j=1;j<i;j++)
         if (x[i]!=x[j]||y[i]!=y[j])
         {
            k++;
            if (x[i]==x[j])  //特判平行于横坐标
            {
                a[k]=0;
                continue;
            }
            if (y[i]==y[j])  //特判平行于纵坐标
            {
                a[k]=10000;
                continue;
            }
            a[k]=(y[i]-y[j])/(x[i]-x[j]);  //求斜率
         }
    }
    sort(a+1,a+1+k);  //排序
    for (int i=2;i<=k;i++)
     if (a[i]!=a[i-1]) sum++;
    return printf("%d\n",sum+1)&0;  //加一是因为第一条线要算上
}