写程序建议事项课件.ppt
1,主题: 初步,写程序建议事项开档技巧指标复习传值与传址,谢谢观赏,2019-8-21,2,变量命名尽可能有意义避免使用指标 (pointers)容易出错尽量使用 global variables 容易实作function 避免使用传址 (call-by-address) 参数尽量使用 function 容易除错,写程序建议事项,谢谢观赏,2019-8-21,3,目前教育部主办的高中信息竞赛要读档以及写入档案ACM Online Judge 全部使用 standard input/output，不开档,开档技巧,谢谢观赏,2019-8-21,4,#includeint main(void)int i;freopen(“data.in”, “r”, stdin);scanf(“%d”, ,#includeint main(void)int i;/freopen(“data.in”, “r”, stdin);scanf(“%d”, ,由档案 data.in 输入(测试与正式比赛),由 stdin 输入(ACM On-line Judge),谢谢观赏,2019-8-21,5,#includeint main(void)int i = 3;freopen(“data.out”, “w”, stdout);printf(“%d”, i);return 0;,#includeint main(void)int i = 3;/ freopen(“data.out”, “w”, stdout);printf(“%d”, i);return 0;,输出到档案 data.out(正式比赛),输出到 stdout(ACM On-line Judge 或测试),谢谢观赏,2019-8-21,6,指标复习 传值与传址,传值 (call-by-value)传值时只传入该变量的值在 function 中更改变量值不会影响呼叫时外面所对应的变量,test(int i) printf(“%d”, i); / i = 3 i = 5; printf(“%d”, i); / i = 5main() int i = 3; test(i); printf(“%d”, i); / i = 3,谢谢观赏,2019-8-21,7,指标复习 传值与传址,传址 (call-by-address)传址时传入该变量的存储器位址(指标)可以经由此位址读取并改写外面变量的值,test(int *i) printf(“%d”, *i); / i = 3 *i = 5; printf(“%d”, *i); / i = 5main() int i = 3; test( / i = 5,谢谢观赏,2019-8-21,8,主题: 简单几何问题,解题技巧题目说明矩形、圆形、三角形、及凸多边形例题讲解: A.476历年题目,谢谢观赏,2019-8-21,9,题目说明,给一点以及一几何图形，判断点是否落在几何图形内,谢谢观赏,2019-8-21,10,Problem 1: 点与矩形,平面上给定一点以及矩形的四顶点坐标，判断该点是否落在矩形内？,x, y,x1, y1,x2, y1,x2, y2,x1, y2,谢谢观赏,2019-8-21,11,Solution: 点与矩形,判断该点是否被矩形的四个顶点包住,x2 x x1, andy2 y y1otherwise,if,yes,no,谢谢观赏,2019-8-21,12,Representations of rectangles,给定左下，右上两顶点给定一顶点及长宽,x1, y1,l,w,x1+l, y1+w,谢谢观赏,2019-8-21,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,谢谢观赏,2019-8-21,14,Problem 2: 点与圆形,平面上给定一点 p 以及圆心 R 坐标及半径 r，判断该点是否落在圆内？,x, y,Rx, Ry,r,谢谢观赏,2019-8-21,15,Solution: 点与圆形,判断该点是否被圆包住,if distance(p, R) ryesotherwiseno,distance(p, R): sqrt(x-Rx)*(x-Rx) + (y-Ry)*(y-Ry),谢谢观赏,2019-8-21,16,Representation of circles,给定圆上三点列出圆心(Rx, Ry)与三点等距方程式解方程式,ax, ay,bx, by,cx, cy,谢谢观赏,2019-8-21,17,|b - a|2 = (bx ax)(bx - ax) + (by - ay)(by - ay)|c - a|2 = (cx ax)(cx - ax) + (cy - ay)(cy - ay),谢谢观赏,2019-8-21,18,Problem 3: 点与三角形,平面上给定一点以及三角形的三顶点坐标，如何判断该点是否落在三角形内？,x, y,x1, y1,x2, y2,x3, y3,谢谢观赏,2019-8-21,19,Solution: 点与三角形,判断该点与三顶点拉线后所形成的三角形面积总合，是否等于原三角形面积(d),x1, y1,x2, y2,x3, y3,a,b,c,if abs(a + b + c d) 0.000001 yesotherwise no,谢谢观赏,2019-8-21,20,给三角形三顶点，计算三角形的面积行列式法,x1, y1,x2, y2,x3, y3,谢谢观赏,2019-8-21,21,行列式的计算结果,谢谢观赏,2019-8-21,22,Problem 4: 点与凸多边形,平面上给定一点以及凸多边形的顶点坐标(顺时针或逆时针)，判断该点是否落在凸多边形内？,x, y,x1, y1,x2, y2,x3, y3,x4, y4,x5, y5,谢谢观赏,2019-8-21,23,Solution: 点与凸多边形,判断该点与各顶点拉线后所形成的三角形面积总合，是否等于原凸多边形面积(f),x1, y1,x2, y2,x3, y3,a,b,c,d,e,x4, y4,x5, y5,谢谢观赏,2019-8-21,24,if abs(a + b + c + d + e - f) 0.000001yesotherwiseno,谢谢观赏,2019-8-21,25,例题讲解: A.476(http:/acm.uva.es/p/v4/476.html),给 n 个矩形，以及平面上的数个点，为每个点判断被哪些矩形给包住,2,3,1,谢谢观赏,2019-8-21,26,Sample Input,r 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-21,27,1,3,2,谢谢观赏,2019-8-21,28,Sample Output,Point 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-21,29,需要的资料结构,int num_fig总共有几个矩形int num_points总共有几个点double xleft11, xright11, yup11, ydown11输入的矩形的左上及右下 x, y 坐标double x, y输入点的 x, y 坐标,谢谢观赏,2019-8-21,30,Program Structure,read_figures();while (read_point() != 0) test_point();,谢谢观赏,2019-8-21,31,read_figures(),read_figures() char fig;num_fig = 0;while(1) scanf(“%c”, /记得将长方形的个数加一 ,谢谢观赏,2019-8-21,32,read_point(),read_point() scanf(“%lf %lf”, ,谢谢观赏,2019-8-21,33,test_point(),void test_point() int i, flag;flag = 0; /纪录是否有被矩形包住过的纪录for(i = 0 ; i x ,谢谢观赏,2019-8-21,34,Program 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();while(read_point() != 0) num_points = num_points + 1;test_point();return 0;,插入所有 functions,谢谢观赏,2019-8-21,35,历年题目,练习题A.478 Points in Figures: Rectangles, Circles, and TrianglesA.10221 SatellitesA.10432 Polygon Inside a Circle (需三角函数)挑战题A.191 Intersection其他历年题目A.378, A.476, A.477, A.190, A.438,谢谢观赏,2019-8-21,
