2015年6月25日 星期四

2015 Google Code Jam Round 1A-Logging

這篇文章應該算是先前這篇的補充。

故事是這樣的，
某一天我在dreamoon的blog看到這篇文章，（當時飲料盃早已結束）
直覺就認為文中的「我在『別人』的網誌上看到對方閱讀了我的 code 覺得不錯」就是我，
於是也跑去嘗試解那題。
（其實就算沒有這段話，我也會去解啦，畢竟也很好奇自己認為不錯的code會有什麼錯誤）


然後結果就是...我雖然往正確的方向思考，但是沒有順利解出來OAO

放棄那題一陣子之後，終於誕生題解了！
（在那篇文章下面我也有回覆，內容不短我就不複製了）

當初Round1A結束的時候，我是有翻一些人的code，
不過當時除了發現用atan2()做極角排序很方便以外，
就是覺得dreamoon那樣的作法超棒、超好寫，
然後就自以為滿足的替這題作結了。

多虧上面這個故事，讓我重新檢視自己的作法。

稍微讀一下我前一篇文章放的code，
就可以發現我的極角排序寫得好複雜，
後面類似sliding window的迴圈更是做了一長串十分多餘的判斷！

當時我會寫成這樣的理由是：
sliding window繞一圈的時候不知道怎麼處理，（也就是測資中的點全都共線的情況）
所以乾脆讓向量們間有嚴格的大小關係。

一個解決方法是上次說的「嘗試最大化不用刪除的點」，
維護「不要太大的最大」比「不要太小的最小」簡單多了XD

另外一個好方法，
就是當極角相等時，把左界儘量往後推，核心的迴圈會變成像這樣：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
for(;l<N-1;l++)
{
    while(l<N-2 && !cmp(use[l],use[l+1]))
        l++;
    if(r<=l)
        r=l+1;
    while(r<l+N-1 && use[l]%use[r]>0)
        r++;
    ans=min(ans,r-l-1);
}

其中cmp()是一個十分良好的極角比較函式，
對於相等的角度會回傳\(false\)，這正是下一段要講的！
極角排序!!!
如同我在dreamoon的blog中回覆的，只要座標範圍達到\(10^8\)，
就算座標都是整數，atan2()的精度也會完全不足！
所以一個只使用外積、內積等能夠完全在整數上操作而沒有誤差的極角排序是必要的！

第一個想到的方法當然就是：寫一個好的比較函式，直接丟給std::sort()。
其實也沒什麼好講的，就是一堆特判，看code比較快@@
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
const PT stu=PT(1,0);
bool cmp(const PT &pa,const PT &pb)
{
    if(stu%pa>0 && stu%pb<0)
        return 1;
    if(stu%pa<0 && stu%pb>0)
        return 0;
    /*************************/
    if(stu%pa==0 && stu*pa>0)
    {
        if(stu%pb==0 && stu*pb>0)
            return 0;
        return 1;
    }
    if(stu%pb==0 && stu*pb>0)
        return 0;
    /*************************/
    return pa%pb>0;
}

註解的那段是...

GCJ這題，寫極角排序漏掉中間那段還是會過XDDD


顯然這樣子對於弧度\(0\)與弧度\(\pi\)的點會被當成角度一樣，
所以這一個generator就可以把這種bug給challenge掉！
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <cstdio>

int main()
{
    printf("1\n");
    int N=1000;
    printf("%d\n",2*N+5);
    for(int x=-1;x<=1;x+=2)
        for(int y=-1;y<=1;y+=2)
            printf("%d %d\n",x,y);
    for(int i=-N;i<=N;i++)
        printf("%d 0\n",i);
    return 0;
}

寫這一個比較函式要很小心OAO


而我，有找到另外一個不錯的作法！
把所有點分兩類，個別排序再合起來
也就是像這樣：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
bool cmp(const PT &pa,const PT &pb)
{
    return pa%pb>0;
}
void sort_vec(vector<PT>& vec)
{
    vector<PT> tmp1,tmp2;
    for(PT u:vec)
    {
        if(u.y>0 || (u.y==0 && u.x>0))
            tmp1.pb(u);
        else
            tmp2.pb(u);
    }
    sort(tmp1.begin(), tmp1.end(), cmp);
    sort(tmp2.begin(), tmp2.end(), cmp);
    vec.clear();
    for(PT u:tmp1) vec.pb(u);
    for(PT u:tmp2) vec.pb(u);
}

此外，如果會出現零向量，要小心處理掉喔！
（GCJ這題沒有這個問題）
最後，則是給上一個可以很方便測試challenge的命令列語法。
challenge是產生測資的執行檔、
target是要被challenge的執行檔，
challenge | target就可以直接把challenge的stdout導向為target的stdin，
可以讓人很方便的測試喔！
dreamoon那篇文章其實是很久之前的事了...
畢業之後耍廢了好一陣子，一直拖到現在才發這篇文= =
張貼者： 於
標籤： ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)