USACO FEB08 Silver Game of Lines 连线游戏
算法一
如果要按题中所给的提示，计算直线的斜率，找出不同斜率的个数，会遇到3个问题。
- 垂直于x轴的直线没有斜率(为无穷大)。
- 有些直线的斜率十分接近，标准数据类型可能会有误差问题。
- 线性查找重复斜率，时间复杂度高达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;
}
上次修改时间 2017-02-03