写程序建议事项.ppt课件.ppt

1、1主题: 初步n写程序建议事项n开档技巧n指标复习传值与传址谢谢观赏2019-8-212n变量命名尽可能有意义n避免使用指标 (pointers)容易出错n尽量使用 global variables 容易实作nfunction 避免使用传址 (call-by-address) 参数n尽量使用 function 容易除错写程序建议事项谢谢观赏2019-8-213n目前教育部主办的高中信息竞赛要读档以及写入档案nACM Online Judge 全部使用 standard input/output，不开档开档技巧谢谢观赏2019-8-214#includeint main(void)int i;f

2、reopen(“data.in”, “r”, stdin);scanf(“%d”, &i);return 0;#includeint main(void)int i;/freopen(“data.in”, “r”, stdin);scanf(“%d”, &i);return 0;由档案 data.in 输入(测试与正式比赛)由 stdin 输入(ACM On-line Judge)谢谢观赏2019-8-215#includeint main(void)int i = 3;freopen(“data.out”, “w”, stdout);printf(“%d”, i);return 0;#inc

3、ludeint main(void)int i = 3;/ freopen(“data.out”, “w”, stdout);printf(“%d”, i);return 0;输出到档案 data.out(正式比赛)输出到 stdout(ACM On-line Judge 或测试)谢谢观赏2019-8-216指标复习 传值与传址n传值 (call-by-value)n传值时只传入该变量的值n在 function 中更改变量值不会影响呼叫时外面所对应的变量test(int i) printf(“%d”, i); / i = 3 i = 5; printf(“%d”, i); / i = 5mai

4、n() int i = 3; test(i); printf(“%d”, i); / i = 3谢谢观赏2019-8-217指标复习 传值与传址n传址 (call-by-address)n传址时传入该变量的存储器位址(指标)n可以经由此位址读取并改写外面变量的值test(int *i) printf(“%d”, *i); / i = 3 *i = 5; printf(“%d”, *i); / i = 5main() int i = 3; test(&i); printf(“%d”, i); / i = 5谢谢观赏2019-8-218主题: 简单几何问题n解题技巧n题目说明n矩形、圆形、三角形、

5、及凸多边形n例题讲解: A.476n历年题目谢谢观赏2019-8-219题目说明n给一点以及一几何图形，判断点是否落在几何图形内谢谢观赏2019-8-2110Problem 1: 点与矩形n平面上给定一点以及矩形的四顶点坐标，判断该点是否落在矩形内？x, yx1, y1x2, y1x2, y2x1, y2谢谢观赏2019-8-2111Solution: 点与矩形n判断该点是否被矩形的四个顶点包住x2 x x1, andy2 y y1otherwiseifyesno谢谢观赏2019-8-2112Representations of rectanglesn给定左下，右上两顶点n给定一顶点及长宽x1

6、, y1lwx1+l, y1+w谢谢观赏2019-8-2113n给定对角线交点及长宽n给定一顶点及对角线交点lwx1, y1x1+ l/2, y1+ w/2x1- l/2, y1- w/2x1, y1x2, y22x1-x2, 2y1-y2谢谢观赏2019-8-2114Problem 2: 点与圆形n平面上给定一点 p 以及圆心 R 坐标及半径 r，判断该点是否落在圆内？x, yRx, Ryr谢谢观赏2019-8-2115Solution: 点与圆形n判断该点是否被圆包住if distance(p, R) ryesotherwisenodistance(p, R): sqrt(x-Rx)*(x

7、-Rx) + (y-Ry)*(y-Ry)谢谢观赏2019-8-2116Representation of circlesn给定圆上三点n列出圆心(Rx, Ry)与三点等距方程式n解方程式ax, aybx, bycx, cy谢谢观赏2019-8-2117|b - a|2 = (bx ax)(bx - ax) + (by - ay)(by - ay)|c - a|2 = (cx ax)(cx - ax) + (cy - ay)(cy - ay)谢谢观赏2019-8-2118Problem 3: 点与三角形n平面上给定一点以及三角形的三顶点坐标，如何判断该点是否落在三角形内？ x, yx1, y1x

8、2, y2x3, y3谢谢观赏2019-8-2119Solution: 点与三角形n判断该点与三顶点拉线后所形成的三角形面积总合，是否等于原三角形面积(d)x1, y1x2, y2x3, y3abcif abs(a + b + c d) 0.000001 yesotherwise no谢谢观赏2019-8-2120n给三角形三顶点，计算三角形的面积n行列式法x1, y1x2, y2x3, y32132213221yyyyxxxxd 谢谢观赏2019-8-2121n行列式的计算结果123123211332213221322121yxyxyxyxyxyxyyyyxxxxd谢谢观赏2019-8-21

9、22Problem 4: 点与凸多边形n平面上给定一点以及凸多边形的顶点坐标(顺时针或逆时针)，判断该点是否落在凸多边形内？x, yx1, y1x2, y2x3, y3x4, y4x5, y5谢谢观赏2019-8-2123Solution: 点与凸多边形n判断该点与各顶点拉线后所形成的三角形面积总合，是否等于原凸多边形面积(f)x1, y1x2, y2x3, y3abcdex4, y4x5, y5谢谢观赏2019-8-212413211321.21yyyyyxxxxxfnnif abs(a + b + c + d + e - f) 0.000001yesotherwiseno谢谢观赏2019-

10、8-2125例题讲解: A.476(http:/acm.uva.es/p/v4/476.html)n给 n 个矩形，以及平面上的数个点，为每个点判断被哪些矩形给包住231谢谢观赏2019-8-2126Sample Inputr 8.5 17.0 25.5 -8.5r 0.0 10.3 5.5 0.0r 2.5 12.5 12.5 2.5*2.0 2.04.7 5.36.9 11.220.0 20.017.6 3.2-5.2 -7.89999.9 9999.9左上 x, y 右下 x, y矩形输入结束测试的点测试的点输入结束谢谢观赏2019-8-2127132-10-50510152025302

11、520151050-5-10谢谢观赏2019-8-2128Sample OutputPoint 1 is contained in figure 2Point 2 is contained in figure 2Point 2 is contained in figure 3Point 3 is contained in figure 3Point 4 is not contained in any figurePoint 5 is contained in figure 1Point 6 is not contained in any figure 谢谢观赏2019-8-2129需要的资料结

12、构nint num_fign总共有几个矩形nint num_pointsn总共有几个点ndouble xleft11, xright11, yup11, ydown11n输入的矩形的左上及右下 x, y 坐标ndouble x, yn输入点的 x, y 坐标谢谢观赏2019-8-2130Program Structureread_figures();while (read_point() != 0) test_point();谢谢观赏2019-8-2131read_figures()read_figures() char fig;num_fig = 0;while(1) scanf(“%c”,

13、 &fig); /读第一个字母读第一个字母if(fig = *) break; /如果是如果是 *，代表长方形的输入结束，代表长方形的输入结束else scanf(“%lf %lf %lf %lfn”, &xleftnum_fig, &yupnum_fig, &xrightnum_fig, &ydownnum_fig);num_fig = num_fig+1; /记得将长方形的个数加一记得将长方形的个数加一 谢谢观赏2019-8-2132read_point()read_point() scanf(“%lf %lf”, &x, &y); if(x = 9999.9 & y = 9999.9)

14、return 0;elsereturn 1;谢谢观赏2019-8-2133test_point()void test_point() int i, flag;flag = 0; /纪录是否有被矩形包住过的纪录纪录是否有被矩形包住过的纪录for(i = 0 ; i num_fig ; i = i+1) /*长方形的编号是从长方形的编号是从 1 开始的开始的*/ if(xlefti x & ydowni y) /*被包住的条件被包住的条件*/ printf(“Point %d is contained in figure %dn”, num_points, i+1);flag = 1;if(fla

15、g = 0) printf(“Point %d is not contained in any figuren”, num_points);谢谢观赏2019-8-2134Program main#includedouble 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()

16、;while(read_point() != 0) num_points = num_points + 1;test_point();return 0;插入所有 functions谢谢观赏2019-8-2135历年题目n练习题nA.478 Points in Figures: Rectangles, Circles, and TrianglesnA.10221 SatellitesnA.10432 Polygon Inside a Circle (需三角函数)n挑战题nA.191 Intersectionn其他历年题目nA.378, A.476, A.477, A.190, A.438谢谢观赏2019-8-21