about makefile with vim

現在小弟來說Makefile檔:
我們先建立一個簡單的程式: 名為 hello.c
如何寫一個最簡單的Makefile檔來編譯它?
# vim Makefile
進入編輯畫面:

# it is a test
all:hello.c
    gcc hello.c -o hello
clean:
    rm -f hello

存檔離開...當我們執行 # make, 就會把名為hello 的執行檔編譯出來
當我們輸入 # make clean, 就會把名為hello 的執行檔給刪除
而Makefile內的#符號指的是註解
ps: 注意: gcc hello.c -o hello 前的空白, 請使用tab鍵,  千萬別使用space鍵喔!!!!

再來複雜一點的:
我們再分別建立a.h, b.h, c.h, main.c, 2.c, 3.c 六個檔案
我們試著編譯它們
# vim Makefile1

mytest:main.o 2.o 3.o
    gcc -o mytest main.o 2.o 3.o
main.o:main.c a.h
    gcc -c main.c
2.o: 2.c a.h b.h
    gcc -c 2.c
3.o:3.c b.h c.h
    gcc -c 3.c

不用擔心, 很容易理解:
當 你打上 # make  -f Makefile1執行後, make就會去找第一行的必要條件: main.o 2.o 3.o, 當在目錄裡卻沒這三個檔, 所以make會在Makefile1往下找main.o/2.o/3.o分別把這三個檔案給編出來, 然後再把mytest這個執行檔給編譯出來, -f 是什麼? 第一次我們已建立一個名Makefile檔, 現在我們又建立一個Makefile1檔, 所以-f是告訴make去執行你所指定的Makefile檔...

再來把上面的變德更複雜一點: 加入變數/if判斷式/install
all: mytest
CC = gcc
INSTDIR = /usr/local/bin
INCLUDE = .
CFLAGS = -g -Wall -ansi

mytest: main.o 2.o 3.o
    $(CC) -o mytest main.o 2.o 3.o
main.o: main.c a.h
    $(CC) -I$(INCLUDE) $(CFLAGS) -c main.c
2.o: 2.c a.h b.h
    $(CC) -I$(INCLUDE) $(CFLAGS) -c 2.c
3.o: 3.c b.h c.h
    $(CC) -I$(INCLUDE) $(CFLAGS) -c 3.c

clean:
    rm main.o 2.o 3.o

install: mytest
    @if[   -d $(INSTDIR)   ]; \
          then   \
          cp mytest $(INSTDIR);\
          chmod a+x $$(INSTDIR)/mytest; \
          chmod og-w $(INSTDIR)/mytest; \
          echo "Installed in $(INSTDIR)";\
    else \
          echo "Sorry, $(INSTDIR) does not exist";\
    fi

哇, 有點多, 不過也一樣很容易理解:
all: mytest 為必要條件, 目錄裡沒有, 就會往下搜mytest: main.o 2.o 3.o
其它的上面已提過

CC = gcc
INSTDIR = /usr/local/bin
INCLUDE = .
CFLAGS = -g -Wall -ansi

此乃變數宣告, 使用變數方式: $(var)
INCLUDE=. 意指目前所在目錄之意

那這些個 -g  -I -Wall是什麼東東?
-ansi : 程式要求依據ansi c標準
-I : 追加include檔案的搜尋路徑 
-Wall : 編譯時顯示所有的警告訊息
-g : 編入除錯資訊(要使用GDB除錯一定要加)

install: 裡面全是shell程式的部份, 未來有空, 小弟會在此詳解
我先說個大概:
@if[   -d $(INSTDIR)   ];
@ 指不要讓make install在執行時, 不要印出執行的細節
另外切記-d前面的空白處及後面R)    ]空白處, 一樣一定要使用tab鍵, 不要使用space
-d 是要make判斷是該檔案是否為目錄且是存在的
cp, 不用說就是copy
chmod a+x 改變mytest 的權限屬性, 意指owner, group, other三個身份都可以執行這個檔案
chmod og-w 改變mytest 的權限屬性, 意指group, other三個身份都不可以編寫修改這個檔案
echo ".." 印出字串
fi 相當於endif的意思

Creative Commons

署名-非商业性使用-相同方式共享 3.0 Unported

您可以自由:

  • 创作演绎作品
  •  

惟须遵守下列条件:

  • 署名您必须按照作者或者许可人指定的方式对作品进行署名。

    What does "Attribute this work" mean?
    The page you came from contained embedded licensing metadata, including how the creator wishes to be attributed for re-use. You can use the HTML here to cite the work. Doing so will also include metadata on your page so that others can find the original work as well.
  • 非商业性使用您不得将本作品用于商业目的。

  • 相同方式共享如果您改变、转换本作品或者以本作品为基础进行创作,您只能采用与本协议相同的许可协议发布基于本作品的演绎作品。

With the understanding that:

  • Waiver — Any of the above conditions can be waived if you get permission from the copyright holder.
  • Other Rights — In no way are any of the following rights affected by the license:
    • Your fair dealing or fair use rights;
    • The author's moral rights;
    • Rights other persons may have either in the work itself or in how the work is used, such as publicity or privacy rights.
  • Notice — 对任何再使用或者发行,您都必须向他人清楚地展示本作品使用的许可协议条款。

转自:http://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh

 

半平面交的O(nlogn)算法[zhuan]

求n个半平面的交有三种做法:

第一种就是用每个平面去切割已有的凸多边形,复杂度O(n^2)。

第二种就是传说中的分治算法。将n个半平面分成两个部分,分别求完交之后再将两个相交的区域求交集。由于交出来的都是凸多边形,利用凸多边形的交可以在O(n)时间内完成的性质,将复杂度降为O(nlogn)。

第三种就是ZZY大牛的那篇论文提到的他自创的排序增量算法。但是他的那种做法还是有些复杂,在网上找到evalls写的一个很优美的版本:(原文地址:http://evalls.yo2.cn/articles/%E5%8D%8A%E5%B9%B3%E9%9D%A2%E4%BA%A4onlogn%E7%9A%84%E7%AE%97%E6%B3%95.html

step1. 将所有半平面按极角排序,对于极角相同的,选择性的保留一个。 O(nlogn)
step2. 使用一个双端队列(deque),加入最开始2个半平面。
step3. 每次考虑一个新的半平面:
a.while deque顶端的两个半平面的交点在当前半平面外:删除deque顶端的半平面
b.while deque底部的两个半平面的交点在当前半平面外:删除deque底部的半平面
c.将新半平面加入deque顶端
step4.删除两端多余的半平面。
具体方法是:
a.while deque顶端的两个半平面的交点在底部半平面外:删除deque顶端的半平面
b.while deque底部的两个半平面的交点在顶端半平面外:删除deque底部的半平面
重复a,b直到不能删除为止。
step5:计算出deque顶端和底部的交点即可。

这个算法描述的非常清晰。当初写的时候有两个地方想的不太明白:step 1如何选择性的保留一个。step3如何判断交点在半平面外。

其实这两个问题都可以用叉积来解决。首先根据给定的两点顺序规定好极角序。假定两点o1o2的输入方向是顺时针,那么另一点P是否在其平面内只要判 断o1P这个向量是否在o1o2这个向量的右手边即可。对于相同角度的两个半平面(a1a2,b1b2),可以看a1b1这个向量是否在a1a2这个向量 的右手边,每次都要选择更靠近右手边的那个半平面。

利用这个算法求多边形的核(PKU 1279),0.00MS,速度还是很快的。