USACO FEB08 Silver Game of Lines 連線遊戲
本文正體字版由OpenCC轉換
算法一
如果要按題中所給的提示，計算直線的斜率，找出不同斜率的個數，會遇到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