USACO FEB08 Silver Game of Lines 连线游戏

算法一

如果要按题中所给的提示,计算直线的斜率,找出不同斜率的个数,会遇到3个问题。

  1. 垂直于x轴的直线没有斜率(为无穷大)。
  2. 有些直线的斜率十分接近,标准数据类型可能会有误差问题。
  3. 线性查找重复斜率,时间复杂度高达O(N^4),只有当算法系数很小时才不会超时。

对于第1个问题,我们可以用0x7FFFFFFF这个数来表示没有斜率。对于第2个问题,我们可以使用double,或者分数表示,判等时绝对值小于等于0.00000001即可。对于第3个问题,我们可以使用平衡树来判重,时间复杂度为O(LogN),总时间复杂度为O(N^2*LogN),不会超时。

这种算法编程不便。

算法二

用向量共线,首先生成(N-1)^2条线段,得到每条线段的向量的坐标表示。

对于向量(x1,y1)和向量(x2,y2),当且仅当x1y2==x2y1时,两向量平行。

枚举得出不平行的直线有多少对即可。

时间复杂度还是O(N^4),但是算法系数很小,可以通过了。

/*
ID: cmykrgb1
PROG: lines
LANG: C++
*/

#include <iostream>
#define MAX 201
#define INF 0x7FFFFFFF
using namespace std;

typedef struct
{
    int x,y;
}point;

point P[MAX],Line[MAX*MAX];
int N,cnt=0;

void init()
{
    int i,j;
    freopen("lines.in","r",stdin);
    freopen("lines.out","w",stdout);
    cin >> N;
    for (i=1;i<=N;i++)
        cin >> P[i].x >> P[i].y;
    for (i=1;i<=N-1;i++)
        for (j=i+1;j<=N;j++)
            Line[++cnt].x=P[j].x-P[i].x,Line[cnt].y=P[j].y-P[i].y;
}

void solve()
{
    int i,j;
    int Ans=1;
    bool b;
    for (i=2;i<=cnt;i++)
    {
        b=true;
        for (j=1;j<i;j++)
            if (Line[i].x*Line[j].y==Line[i].y*Line[j].x)
            {
                b=false;
                break;
            }
        if (b)
            Ans++;
    }
    cout << Ans << endl;
}

int main()
{
    init();
    solve();
    return 0;
}

相关日志