连线游戏【模拟】

题目大意：

游戏开始的时 候，FJ会给贝茜一块画着N个不重合的点的木板，其中第i个点 的横、纵坐标分别为x[i]和y[i]。 贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏 中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

---

思路：

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

---

代码：

#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;  //加一是因为第一条线要算上
}