主题初步.ppt
1,主題: 初步,寫程式建議事項 開檔技巧 指標複習傳值與傳址,2,變數命名儘可能有意義 避免使用指標 (pointers)容易出錯 儘量使用 global variables 容易實作 function 避免使用傳址 (call-by-address) 參數 儘量使用 function 容易除錯,寫程式建議事項,3,目前教育部主辦的高中資訊競賽要讀檔以及寫入檔案 ACM Online Judge 全部使用 standard input/output，不開檔,開檔技巧,4,#include int main(void) int i; freopen(“data.in”, “r”, stdin); scanf(“%d”, ,#include int main(void) int i; /freopen(“data.in”, “r”, stdin); scanf(“%d”, ,由檔案 data.in 輸入 (測試與正式比賽),由 stdin 輸入 (ACM On-line Judge),5,#include int main(void) int i = 3; freopen(“data.out”, “w”, stdout); printf(“%d”, i); return 0; ,#include int main(void) int i = 3; / freopen(“data.out”, “w”, stdout); printf(“%d”, i); return 0; ,輸出到檔案 data.out (正式比賽),輸出到 stdout (ACM On-line Judge 或測試),6,指標複習 傳值與傳址,傳值 (call-by-value) 傳值時只傳入該變數的值 在 function 中更改變數值不會影響呼叫時外面所對應的變數,test(int i) printf(“%d”, i); / i = 3 i = 5; printf(“%d”, i); / i = 5 main() int i = 3; test(i); printf(“%d”, i); / i = 3 ,7,指標複習 傳值與傳址,傳址 (call-by-address) 傳址時傳入該變數的記憶體位址(指標) 可以經由此位址讀取並改寫外面變數的值,test(int *i) printf(“%d”, *i); / i = 3 *i = 5; printf(“%d”, *i); / i = 5 main() int i = 3; test( / i = 5 ,8,主題: 簡單幾何問題,解題技巧 題目說明 矩形、圓形、三角形、及凸多邊形 例題講解: A.476 歷年題目,9,題目說明,給一點以及一幾何圖形，判斷點是否落在幾何圖形內,10,Problem 1: 點與矩形,平面上給定一點以及矩形的四頂點座標，判斷該點是否落在矩形內？,x, y,x1, y1,x2, y1,x2, y2,x1, y2,11,Solution: 點與矩形,判斷該點是否被矩形的四個頂點包住,x2 x x1, and y2 y y1 otherwise,if,yes,no,12,Representations of rectangles,給定左下，右上兩頂點 給定一頂點及長寬,x1, y1,l,w,x1+l, y1+w,13,給定對角線交點及長寬 給定一頂點及對角線交點,l,w,x1, y1,x1+ l/2, y1+ w/2,x1- l/2, y1- w/2,x1, y1,x2, y2,2x1-x2, 2y1-y2,14,Problem 2: 點與圓形,平面上給定一點 p 以及圓心 R 座標及半徑 r，判斷該點是否落在圓內？,x, y,Rx, Ry,r,15,Solution: 點與圓形,判斷該點是否被圓包住,if distance(p, R) r yes otherwise no,distance(p, R): sqrt(x-Rx)*(x-Rx) + (y-Ry)*(y-Ry),16,Representation of circles,給定圓上三點 列出圓心(Rx, Ry)與三點等距方程式 解方程式,ax, ay,bx, by,cx, cy,17,|b - a|2 = (bx ax)(bx - ax) + (by - ay)(by - ay) |c - a|2 = (cx ax)(cx - ax) + (cy - ay)(cy - ay),18,Problem 3: 點與三角形,平面上給定一點以及三角形的三頂點座標，如何判斷該點是否落在三角形內？,x, y,x1, y1,x2, y2,x3, y3,19,Solution: 點與三角形,判斷該點與三頂點拉線後所形成的三角形面積總合，是否等於原三角形面積(d),x1, y1,x2, y2,x3, y3,a,b,c,if abs(a + b + c d) 0.000001 yes otherwise no,20,給三角形三頂點，計算三角形的面積 行列式法,x1, y1,x2, y2,x3, y3,21,行列式的計算結果,22,Problem 4: 點與凸多邊形,平面上給定一點以及凸多邊形的頂點座標(順時針或逆時針)，判斷該點是否落在凸多邊形內？,x, y,x1, y1,x2, y2,x3, y3,x4, y4,x5, y5,23,Solution: 點與凸多邊形,判斷該點與各頂點拉線後所形成的三角形面積總合，是否等於原凸多邊形面積(f),x1, y1,x2, y2,x3, y3,a,b,c,d,e,x4, y4,x5, y5,24,if abs(a + b + c + d + e - f) 0.000001 yes otherwise no,25,例題講解: A.476 (http:/acm.uva.es/p/v4/476.html),給 n 個矩形，以及平面上的數個點，為每個點判斷被哪些矩形給包住,2,3,1,26,Sample Input,r 8.5 17.0 25.5 -8.5 r 0.0 10.3 5.5 0.0 r 2.5 12.5 12.5 2.5 * 2.0 2.0 4.7 5.3 6.9 11.2 20.0 20.0 17.6 3.2 -5.2 -7.8 9999.9 9999.9,左上 x, y 右下 x, y,矩形輸入結束,測試的點,測試的點輸入結束,27,1,3,2,28,Sample Output,Point 1 is contained in figure 2 Point 2 is contained in figure 2 Point 2 is contained in figure 3 Point 3 is contained in figure 3 Point 4 is not contained in any figure Point 5 is contained in figure 1 Point 6 is not contained in any figure,29,需要的資料結構,int num_fig 總共有幾個矩形 int num_points 總共有幾個點 double xleft11, xright11, yup11, ydown11 輸入的矩形的左上及右下 x, y 座標 double x, y 輸入點的 x, y 座標,30,Program Structure,read_figures(); while (read_point() != 0) test_point(); ,31,read_figures(),read_figures() char fig; num_fig = 0; while(1) scanf(“%c”, /記得將長方形的個數加一 ,32,read_point(),read_point() scanf(“%lf %lf”, ,33,test_point(),void test_point() int i, flag; flag = 0; /紀錄是否有被矩形包住過的紀錄 for(i = 0 ; i x ,34,Program main,#include double xleft11, xright11, yup11, ydown11, x, y; int num_fig, num_points; int main(void) freopen(“data.txt”, “r”, stdin);/若送到acm online judge，這行拿掉 num_points = 0; /紀錄總共有幾點 read_figures(); while(read_point() != 0) num_points = num_points + 1; test_point(); return 0; ,插入所有 functions,35,歷年題目,練習題 A.478 Points in Figures: Rectangles, Circles, and Triangles http:/acm.uva.es/p/v4/478.html A.10221 Satellites http:/acm.uva.es/p/v102/10221.html A.10432 Polygon Inside a Circle (需三角函數) http:/acm.uva.es/p/v104/10432.html 挑戰題 A.191 Intersection http:/acm.uva.es/p/v1/191.html 其他歷年題目 A.378, A.476, A.477, A.190, A.438,
