[計算幾何]USACO Feb08 USACO Silver Game of Lines 連線遊戲

Title: 連線遊戲

Input: lines.in

Output: lines.out

Time Limit: 1000 ms

Memory Limit: 16 MB

Level: ★☆

Farmer John最近發明瞭一個遊戲，來考驗自命不凡的貝茜。遊戲開始的時候，FJ會給貝茜一塊畫著N (2 <= N <= 200)個不重合的點的木板，其中第i個點的橫、縱座標分別為X_i和Y_i (-1,000 <= X_i <=1,000；-1,000 <= Y_i <= 1,000)。

貝茜可以選兩個點畫一條過它們的直線，當且僅當平面上不存在與畫出直線平行的直線。遊戲結束時貝茜的得分，就是她畫出的直線的總條數。為了在遊戲中勝出，貝茜找到了你，希望你幫她計算一下最大可能得分。

程序名: lines

 

輸入格式:

• 第1行: 輸入1個正整數：N

• 第2..N+1行: 第i+1行用2個用空格隔開的整數X_i、Y_i，描述了點i的座標

輸入樣例 (lines.in):

4

-1 1

-2 0

0 0

1 1

輸出格式:

• 第1行: 輸出1個整數，表示貝茜的最大得分，即她能畫出的互不平行的直線數

輸出樣例 (lines.out):

4

輸出說明:

貝茜能畫出以下4種斜率的直線：-1，0，1/3以及1。

【分析】

這是一道簡單的計算幾何的題目。雖然題目很簡單，就是讓你求斜率不同的直線的個數。

首先要單獨考慮斜率不存在的情況，也就是與Y軸平行的直線，因為它的斜率是無窮大，

導致在計算過程中會出現除數為0的情況，所以要單獨考慮。

本題關鍵是在於斜率的判重。

我一開始是直接掛上set容器，由於set是『集合』，不會出現重複的元素，所以可以利用這一點來判重。這樣插入的時間複雜度為O(N*LogN)，不會超時。但是，我這樣寫僅僅能在Windows下AC、在Ubuntu 11.10下AC，在NOI Linux（Ubuntu 9.04）下會出現WA 6組的情況～可能是由於實數的精度問題吧。

後來，我打算不直接存儲斜率了，由於每條斜率的直線可以化為兩個正整數之比，所以我直接存儲斜率的分子和分母。  開2000個平衡樹（就是set容器了），如果斜率為負，就把負號移到分子上，保證分母是正數，然後…… set[分母].insert(分子)，就這樣，利用set容器的特性來幫你判重。最後統計每個set容器的size()即可，注意不要忘記考慮斜率無窮大的情況。

我在昨晚這題後，為了向神牛學習，參看了BYVoid神牛的解題報告 ，他是用的向量共線來判重。只不過時間複雜度有點高，他的程序在COGS上的運行時間為1.6秒，我的程序是0.16秒。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25575

01 /*
02 *Problem: USACO Feb08 Silver lines
03 *Author: Yee-fan Zhu
04 *Email: zyfworks@gmail.com
05 *Method: Computer Aided Geometric Design
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 #include <set>
10 #include <algorithm>
11 using namespace std;
12 const int MAXN=201;
13 bool NoTangent=false;
14 bool TanZero=false;
15 class Point
16 {
17 public:
18     int x,y;
19 }P[MAXN];
20
21 int N;
22 set<int>tan[2001];
23
24 void init()
25 {
26     scanf("%d\n",&N);
27     for(int i=1;i<=N;i++)
28         scanf("%d %d\n",&P[i].x,&P[i].y);
29 }
30
31 int Min(int a,int b)
32 {
33     return a>b?b:a;
34 }
35
36 int Abs(int a)
37 {
38     return a>=0?a:-a;
39 }
40
41 void check(int m,int n)
42 {   
43     int x=P[n].x-P[m].x;
44     int y=P[n].y-P[m].y;
45     if(x==0)
46     {
47         NoTangent=true;
48         return;
49     }
50     if(y==0)
51     {
52         TanZero=true;
53         return;
54     }
55     bool fu=( (x<0 && y>0) || (x>0 && y<0) );
56     x=Abs(x),y=Abs(y);
57     int tmp=Min(x,y);
58     for(int i=2;i<=tmp;i++)
59     {
60         while(x%i==0 && y%i==0)
61         {
62             x/=i,y/=i;
63         }
64     }
65     if(fu)
66         x=-x;
67     tan[y].insert(x);
68 }
69
70 void solve()
71 {
72     for(int i=1;i<=N;i++)
73         for(int j=i+1;j<=N;j++)
74             check(i,j);
75     int Ans=0;
76     for(int i=1;i<=2000;i++)
77         Ans+=(tan[i].size());
78     printf("%d\n",Ans+NoTangent+TanZero);   
79 }
80
81 int main()
82 {
83     freopen("lines.in","r",stdin);
84     freopen("lines.out","w",stdout);
85     init();
86     solve();
87     return 0;
88 }