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;freop
2、en(“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;#includeint main(vo
3、id)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=5main()int i=3;test(i);printf(“%d”,i);/i
4、=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矩形、圆形、三角形、及凸多边形n例题讲解:A.476n历年题目谢谢观赏2019-8-219题目说明n给一点以及一几何图形，判断点是否落在几何图形内谢谢观赏2019-8
5、-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,y1lwx1+l,y1+w谢谢观赏2019-8-2113n给定对角线交点及长宽n给定一顶点及对角线交点lwx1,y1x1+l/2,y1+w/2x1-l/2,y1-
6、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-Rx)+(y-Ry)*(y-Ry)谢谢观赏2019-8-2116Representation of circlesn给定圆上三点n列出圆心(Rx,Ry)与三点等距方程式n解方程式ax,aybx,bycx
7、,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,y1x2,y2x3,y3谢谢观赏2019-8-2119Solution:点与三角形n判断该点与三顶点拉线后所形成的三角形面积总合，是否等于原三角形面积(d)x1,y1x2,y2x3,y3abcif abs(a+b+c d)0.000001 yesotherwise no谢谢观赏
8、2019-8-2120n给三角形三顶点，计算三角形的面积n行列式法x1,y1x2,y2x3,y32132213221yyyyxxxxd 谢谢观赏2019-8-2121n行列式的计算结果123123211332213221322121yxyxyxyxyxyxyyyyxxxxd谢谢观赏2019-8-2122Problem 4:点与凸多边形n平面上给定一点以及凸多边形的顶点坐标(顺时针或逆时针)，判断该点是否落在凸多边形内？x,yx1,y1x2,y2x3,y3x4,y4x5,y5谢谢观赏2019-8-2123Solution:点与凸多边形n判断该点与各顶点拉线后所形成的三角形面积总合，是否等于原凸多
9、边形面积(f)x1,y1x2,y2x3,y3abcdex4,y4x5,y5谢谢观赏2019-8-212413211321.21yyyyyxxxxxfnnif abs(a+b+c+d+e-f)0.000001yesotherwiseno谢谢观赏2019-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.
10、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-50510152025302520151050-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 i
11、s not contained in any figurePoint 5 is contained in figure 1Point 6 is not contained in any figure 谢谢观赏2019-8-2129需要的资料结构nint num_fign总共有几个矩形nint num_pointsn总共有几个点ndouble xleft11,xright11,yup11,ydown11n输入的矩形的左上及右下 x,y 坐标ndouble x,yn输入点的 x,y 坐标谢谢观赏2019-8-2130Program Structureread_figures();while(rea
12、d_point()!=0)test_point();谢谢观赏2019-8-2131read_figures()read_figures()char fig;num_fig=0;while(1)scanf(“%c”,&fig);/读第一个字母读第一个字母if(fig=*)break;/如果是如果是*，代表长方形的输入结束，代表长方形的输入结束else scanf(“%lf%lf%lf%lfn”,&xleftnum_fig,&yupnum_fig,&xrightnum_fig,&ydownnum_fig);num_fig=num_fig+1;/记得将长方形的个数加一记得将长方形的个数加一 谢谢观赏
13、2019-8-2132read_point()read_point()scanf(“%lf%lf”,&x,&y);if(x=9999.9&y=9999.9)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
14、contained in figure%dn”,num_points,i+1);flag=1;if(flag=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_p
15、oints=0;/纪录总共有几点纪录总共有几点read_figures();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
