《主题初步.ppt》由会员分享，可在线阅读，更多相关《主题初步.ppt（35页珍藏版）》请在三一文库上搜索。
1、主題: 初步 n寫程式 建議事項 n開檔技巧 n指標複習 傳值與傳址 蜘 穗 迁 舆 奋 令 储 生 双 掉 寥 悸 问 晃 苗 箍 滔 箍 愚 伏 蜜 队 课 拌 蹿 贺 春 加 卫 碑 衅 妒 主 题 初 步 主 题 初 步 1 n變數命名儘可能有意義 n避免使用指標 (pointers)容易出錯 n儘量使用 global variables 容易實作 nfunction 避免使用傳址 (call-by-address) 參 數 n儘量使用 function 容易除錯 寫程式 建議事項 谬 些 藏 寥 缅 囚 爷 惮 腆 啤 嗣 甫 怒 映 哄 挝 阀 痞 攻 所 乞 撼 雷 玛 材 宦
2、讹 棘 乡 迄 谈 堕 主 题 初 步 主 题 初 步 2 n目前教育部主辦的高中資訊競賽要讀 檔以及寫入檔案 nACM Online Judge 全部使用 standard input/output，不開檔 開檔技巧 断 矢 碴 堪 赃 诛 站 涎 彪 背 狭 端 稗 煽 惭 曾 拙 邯 乖 祸 级 蓖 库 祁 邑 诱 窟 祈 酱 谷 掸 撑 主 题 初 步 主 题 初 步 3 #include int main(void) int i; freopen(“data.in”, “r”, stdin); scanf(“%d”, return 0; #include int main(void)
3、 int i; /freopen(“data.in”, “r”, stdin); scanf(“%d”, return 0; 由檔案 data.in 輸入 (測試與正式比賽 ) 由 stdin 輸入 (ACM On-line Judge) 韦 屹 扁 合 铆 又 监 步 踌 挛 攘 啪 翁 庭 俭 胃 递 汤 邀 媳 计 补 晓 绵 爹 搅 融 稳 脑 炎 侄 汾 主 题 初 步 主 题 初 步 4 #include int main(void) int i = 3; freopen(“data.out”, “w”, stdout); printf(“%d”, i); return 0; #i
4、nclude int main(void) int i = 3; / freopen(“data.out”, “w”, stdout); printf(“%d”, i); return 0; 輸出到檔案 data.out (正式比賽 ) 輸出到 stdout (ACM On-line Judge 或測試 ) 自 吨 贬 勿 蛙 矾 续 锣 蓖 闲 拇 拦 荚 谗 颐 辆 徊 崖 啪 时 袜 聘 违 悦 堕 伶 屋 虚 鄂 何 瑞 茁 主 题 初 步 主 题 初 步 5 指標複習 傳值與傳址 n傳值 (call-by-value) n傳值時只傳入該變 數的值 n在 function 中更改變 數
5、值不會影響呼叫 時外面所 對應的變 數 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 寇 拎 皱 颅 盎 兜 缓 盆 支 悦 魄 裳 壹 鸭 荡 俯 甘 盈 祈 糖 贸 嚼 抡 捣 哀 润 碱 阐 昨 朽 影 绊 主 题 初 步 主 题 初 步 6 指標複習 傳值與傳址 n傳址 (call-by- address) n傳址時傳入該變數 的記憶體位址 (指標) n可以經由此位址讀 取並改寫外面變數 的值
6、 test(int *i) printf(“%d”, *i); / i = 3 *i = 5; printf(“%d”, *i); / i = 5 main() int i = 3; test( printf(“%d”, i); / i = 5 钵 帮 磕 腐 鞠 勇 辰 簿 敦 沪 壤 闻 亏 遁 挨 木 费 耗 沤 演 沂 念 浙 逾 蚁 慕 御 稿 价 峦 刚 犊 主 题 初 步 主 题 初 步 7 主題: 簡單幾何問題 n解題技巧 n題目說明 n矩形、圓形、三角形、及凸多邊形 n例題講解 : A.476 n歷年題目 砰 疼 舔 纵 瓶 侣 鼎 秸 稻 进 迪 汁 泥 吾 归 梧 洱 言
7、 墒 菏 根 戍 策 诣 议 极 瘩 希 胸 长 尘 陵 主 题 初 步 主 题 初 步 8 題目說明 n給一點以及一幾何圖形，判斷點是否 落在幾何圖形內 烫 蝗 辫 亨 苟 咒 琐 象 躺 迢 讼 妨 亲 馅 语 纂 饯 馋 别 联 橡 类 砧 勒 缨 驭 砂 佣 葫 烟 综 掀 主 题 初 步 主 题 初 步 9 Problem 1: 點與矩形 n平面上給定一點以及矩形的四頂點座 標，判斷該點是否落在矩形內？ x, y x1, y1x2, y1 x2, y2x1, y2 请 烦 胳 葬 宾 檀 眩 柴 孝 烟 螺 平 疙 庭 蕉 紧 皿 竞 锣 纽 逸 泊 抵 烽 母 龚 谬 进 刽 着
8、搀 巾 主 题 初 步 主 题 初 步 10 Solution: 點與矩形 n判斷該點是否被矩形的四個頂點包住 x2 x x1, and y2 y y1 otherwise if yes no 骑 帖 孰 凯 妈 软 屏 盾 赛 莫 肮 佬 派 弊 谁 包 脊 山 叶 村 药 蠕 疽 爵 搪 熄 痉 薪 链 蓝 坞 晾 主 题 初 步 主 题 初 步 11 Representations of rectangles n給定左下，右上兩頂點 n給定一頂點及長寬 x1, y1 l w x1+l, y1+w 诬 木 梭 吓 译 滚 舍 耽 伯 铱 谨 骚 铝 肄 恤 拽 屎 宙 哎 佛 乔 拐 磅
9、舒 财 顿 斋 帮 吧 衣 撰 泣 主 题 初 步 主 题 初 步 12 n給定對角線交點及長寬 n給定一頂點及對角線交點 l w x1, y1 x1+ l/2, y1+ w/2 x1- l/2, y1- w/2 x1, y1 x2, y2 2x1-x2, 2y1-y2 邪 好 唐 注 郑 枉 帅 舱 谁 乔 棠 涤 涵 拓 凤 烟 迅 惋 杉 班 喇 术 鲸 爹 窘 蓑 暖 故 板 簇 是 蝎 主 题 初 步 主 题 初 步 13 Problem 2: 點與圓形 n平面上給定一點 p 以及圓心 R 座標及 半徑 r，判斷該點是否落在圓內？ x, yRx, Ry r 坊 呈 椒 耘 傣 白 谈
10、 恫 诅 辊 饵 锗 敖 婿 飞 剥 荚 泰 邹 痊 净 污 掂 剃 砌 邱 拂 沾 厩 粒 立 羔 主 题 初 步 主 题 初 步 14 Solution: 點與圓形 n判斷該點是否被圓包住 if distance(p, R) ryes otherwiseno distance(p, R): sqrt(x-Rx)*(x-Rx) + (y-Ry)*(y-Ry) 英 罕 浓 方 藩 捏 妇 爬 牵 竞 询 衅 切 妥 鹤 寺 厂 态 涝 刮 碳 狮 困 驻 营 疗 束 溢 格 扦 节 壁 主 题 初 步 主 题 初 步 15 Representation of circles n給定圓上三點 n
11、列出圓心 (Rx, Ry)與三點等距方程式 n解方程式 ax, ay bx, by cx, cy 腊 携 瞧 预 向 朴 缅 仔 拟 摊 到 水 更 哉 执 氮 恭 朔 猴 峦 非 入 究 何 谣 妮 怎 锚 罗 众 寐 仓 主 题 初 步 主 题 初 步 16 |b - a|2 = (bx ax)(bx - ax) + (by - ay)(by - ay) |c - a|2 = (cx ax)(cx - ax) + (cy - ay)(cy - ay) 莆 苏 操 嘶 吐 翠 洒 弛 慕 贿 毯 顽 穴 春 颧 傈 奉 捅 挤 桌 啼 豢 愁 疲 易 准 俱 考 旺 烃 闷 蔬 主 题 初
12、步 主 题 初 步 17 Problem 3: 點與三角形 n平面上給定一點以及三角形的三頂點 座標，如何判斷該點是否落在三角形 內？ x, y x1, y1 x2, y2 x3, y3 墓 等 喉 冉 鞠 鄂 纺 合 椭 某 赶 胀 插 移 苑 书 忱 远 绰 塑 哥 兼 烂 稿 捶 矣 劝 铡 竭 驹 值 揩 主 题 初 步 主 题 初 步 18 Solution: 點與三角形 n判斷該點與三頂點拉線後所形成的三 角形面積總合，是否等於原三角形面 積(d) x1, y1 x2, y2 x3, y3 a b c if abs(a + b + c d) 0.000001 yes otherwi
13、se no 雅 酗 楼 磕 芋 资 烦 册 沫 会 粳 恩 丽 邮 赚 她 砍 预 泼 酣 严 涉 诽 协 柔 鳖 蔗 弯 贵 琳 蝶 胯 主 题 初 步 主 题 初 步 19 n給三角形三頂點，計算三角形的面積 n行列式法 x1, y1 x2, y2 x3, y3 羹 除 虎 疮 页 羊 氯 往 宠 薪 瘩 贬 虏 厢 这 蒸 呆 挪 筐 沿 企 宙 洋 鬼 滴 屡 胆 柿 掌 墨 干 副 主 题 初 步 主 题 初 步 20 n行列式的計算結果 蝴 呜 诱 聘 远 偷 跃 炎 正 潘 乖 亭 共 过 煎 经 赎 麦 催 兆 斩 迈 缴 凛 迄 贩 予 斟 镐 锯 贾 粘 主 题 初 步 主
14、 题 初 步 21 Problem 4: 點與凸多邊形 n平面上給定一點以及凸多邊 形的頂點 座標 (順時針或逆時針 )，判斷該點是 否落在 凸多邊 形內？ x, y x1, y1 x2, y2 x3, y3 x4, y4 x5, y5 阁 臆 唱 典 汹 橡 时 墓 摄 唯 蔗 泡 卡 篙 膊 企 瞬 彬 泛 户 慑 寨 饮 待 傀 仰 橱 烈 蕉 耿 游 售 主 题 初 步 主 题 初 步 22 Solution: 點與凸多邊形 n判斷該點與各頂點拉線後所形成的三 角形面積總合，是否等於原凸多邊形 面積 (f) x1, y1 x2, y2 x3, y3 a b c d e x4, y4 x
15、5, y5 亿 努 邀 潞 丙 摹 仇 天 唾 聊 怒 滚 焰 势 级 郝 还 卞 涌 县 闽 辐 锅 擅 霸 皱 翟 慑 拒 华 鸡 猪 主 题 初 步 主 题 初 步 23 if abs(a + b + c + d + e - f) 0.000001yes otherwiseno 税 添 悬 郧 橡 虞 战 琐 醇 胯 河 哥 染 靖 扁 蝗 漳 恭 诡 皮 稍 占 省 夕 帜 住 顺 虐 怔 废 冗 惊 主 题 初 步 主 题 初 步 24 例題講解 : A.476 (http:/acm.uva.es/p/v4/476.html) n給 n 個矩形，以及平面上的數個點， 為每個點判斷被哪
16、些矩形給包住 2 3 1 楷 促 暇 玻 瞻 李 宏 趾 裂 矿 幂 甘 封 圃 嗓 订 龄 岛 厩 诅 欧 竖 蚁 积 捐 袒 凹 甄 赃 哩 我 眶 主 题 初 步 主 题 初 步 25 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 矩形輸入結束 測試的點 測試的點輸入結束 宫 巨 羊 羊 字 答 承 李 兜 挽 狰 繁
17、娥 瑟 褒 喘 薄 另 胯 獭 工 菠 堡 佃 拧 昏 轧 戮 粘 摸 规 选 主 题 初 步 主 题 初 步 26 1 3 2 -10-5051015202530 25 20 15 10 5 0 -5 -10 爬 来 迹 漆 刮 摆 帝 辅 慑 榷 柜 示 革 减 吱 据 湿 盂 辉 涧 符 镇 您 棕 搬 韶 庆 库 双 姿 剔 摊 主 题 初 步 主 题 初 步 27 Sample Output Point 1 is contained in figure 2 Point 2 is contained in figure 2 Point 2 is contained in figure
18、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 准 坑 舍 寓 抛 焦 赘 青 林 厄 俭 帛 闻 锯 遵 雹 殃 终 存 结 雁 褪 肘 屋 崇 什 疽 偏 沟 喂 即 陛 主 题 初 步 主 题 初 步 28 需要的資料結構 nint num_fig n總共有幾個矩形 nint num_points n總共有幾個點 ndouble xleft11,
19、xright11, yup11, ydown11 n輸入的矩形的左上及右下 x, y 座標 ndouble x, y n輸入點的 x, y 座標 滨 短 弟 衬 类 链 团 先 值 骇 具 翔 脱 批 昂 钒 部 贷 修 诣 运 们 梅 销 令 侧 关 号 雌 挖 喘 井 主 题 初 步 主 题 初 步 29 Program Structure read_figures(); while (read_point() != 0) test_point(); 臭 灿 弦 堕 湃 纤 洗 婆 久 岳 授 推 鲤 跺 圆 杭 杏 甸 妆 鹿 撅 松 酋 厦 算 盔 盗 盼 颠 代 臼 衣 主 题 初
20、步 主 题 初 步 30 read_figures() read_figures() char fig; num_fig = 0; while(1) scanf(“%c”, /讀第一個字母讀第一個字母 if(fig = *) break; /如果是如果是 *，代表長方形的輸入結束，代表長方形的輸入結束 else scanf(“%lf %lf %lf %lfn”, num_fig = num_fig+1; /記得將長方形的個數加一記得將長方形的個數加一 莎 养 雕 匿 傅 拘 睬 虾 韧 煮 付 昧 见 皿 什 檄 领 挑 逐 帆 骨 驹 巾 崖 梨 材 壳 蛊 氏 炔 聚 玻 主 题 初 步
21、主 题 初 步 31 read_point() read_point() scanf(“%lf %lf”, if(x = 9999.9 else return 1; 炼 补 缩 艰 火 伸 银 靶 诞 瞒 灯 危 凭 柑 哈 挖 纠 椽 椭 室 良 骋 稳 喷 锚 驳 懂 婴 氓 四 孙 慕 主 题 初 步 主 题 初 步 32 test_point() void test_point() int i, flag; flag = 0; /紀錄是否有被矩形包住過的紀錄紀錄是否有被矩形包住過的紀錄 for(i = 0 ; i num_fig ; i = i+1) /*長方形的編號是從長方形的編號是
22、從 1 開始的開始的 */ if(xlefti x flag = 1; if(flag = 0) printf(“Point %d is not contained in any figuren”, num_points); 矗 掠 绪 沃 螟 蔑 嫉 寒 翁 赚 找 链 璃 肉 踊 奄 详 伶 帧 照 轿 头 师 坦 嫌 鹊 遗 咀 欠 虫 沪 舜 主 题 初 步 主 题 初 步 33 Program main #include double xleft11, xright11, yup11, ydown11, x, y; int num_fig, num_points; int main(
23、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 沸 鲍 边 忽 鲜 眶 渠 簇 捆 翌 菇 雾 撑 续 攘 懈 陛 腋 翅 演 落 沽 表 峡 宙 底 吾 剪 未 稗 依 皇 主 题 初 步 主 题 初 步 34 歷年題目
24、 n練習題 nA.478 Points in Figures: Rectangles, Circles, and Triangles nhttp:/acm.uva.es/p/v4/478.html nA.10221 Satellites nhttp:/acm.uva.es/p/v102/10221.html nA.10432 Polygon Inside a Circle (需三角函數 ) nhttp:/acm.uva.es/p/v104/10432.html n挑戰題 nA.191 Intersection nhttp:/acm.uva.es/p/v1/191.html n其他歷年題目 nA.378, A.476, A.477, A.190, A.438 的 栅 妥 效 吭 被 噪 泄 裔 踊 灵 彬 坛 瞻 起 接 弘 铜 苞 邮 诱 伐 潍 萧 煎 趣 仙 搪 建 接 绍 脑 主 题 初 步 主 题 初 步 35