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
您可以自由:
- 复制、发行、展览、表演、放映、广播或通过信息网络传播本作品
- 创作演绎作品
惟须遵守下列条件:
-
署名 — 您必须按照作者或者许可人指定的方式对作品进行署名。
-
非商业性使用 — 您不得将本作品用于商业目的。
-
相同方式共享 — 如果您改变、转换本作品或者以本作品为基础进行创作,您只能采用与本协议相同的许可协议发布基于本作品的演绎作品。
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:
- 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,速度还是很快的。