478-Points in Figures: Rectangles, Circles and Triangles

<br /> /* <br /> "Points in Figures: Rectangles, Circles and Triangles"<br /> Level:5.0<br /> Date:2006/9/11<br /> 技巧：<br /> 　長方形的判斷: x > 左上角的x && x < 右下角的x && y < 左上角的y && y > 右下角的y<br /> 圓形的判斷: (x - 圓心的x)^2 + (y - 圓心的y)^2 < 半徑^2 三角形的判斷: 面積比較法:若點在三角形內 ,則點與三頂點將形成三個三角形, 若其面積總和 > 原三角形面積 ,且誤差小於0.000001, 則點在三角形內 <br /> 此法非最佳, 利用向量判斷是否線段相交, 不但較快, 也較省記憶體.<br /> */<br /> <br /> #include <stdio.h><br /> #include <math.h><br /> <br /> struct shape{<br /> char kind; //rectangle, circle or triangle<br /> double x1;<br /> double y1;<br /> double x2;<br /> double y2;<br /> 　　 double x3;<br /> double y3;<br /> double radius;<br /> }s[10];<br /> <br /> double length(double x1, double y1, double x2, double y2); <br /> double area(double a, double b, double c); //apply Heron's rule to calculate Triangle's Area.<br /> <br /> main(){<br /> const float epsilon = 0.000001; // use epsilon to guard against miscalculation.<br /> double t1,t2,t3,t0; 　 // calculate the area of triangles.<br /> int i;<br /> int no=1;<br /> bool contain = false;<br /> int len = 0;<br /> double x,y;<br /> char temp;<br /> while(scanf("%c",&temp)){<br /> if(temp == 'r'){<br /> scanf("%lf %lf %lf %lf",&s[len].x1,&s[len].y1,<br /> &s[len].x2,&s[len].y2);<br /> s[len].kind = 'r'; <br /> s[len].radius = 0;<br /> s[len].x3 = 0;<br /> s[len].y3 = 0;<br /> len++;<br /> }<br /> else if (temp == 'c'){<br /> scanf("%lf %lf %lf", &s[len].x1, &s[len].y1, &s[len].radius);<br /> s[len].kind = 'c';<br /> s[len].x2 = s[len].y2 = s[len].x3 = s[len].y3 = 0;<br /> len++;<br /> } <br /> else if (temp == 't'){<br /> scanf("%lf %lf %lf %lf %lf %lf", <br /> 　　　　　　　　　&s[len].x1, &s[len].y1, &s[len].x2, &s[len].y2, &s[len].x3, &s[len].y3);<br /> s[len].kind = 't';<br /> s[len].radius = 0;<br /> len++;<br /> } <br /> else if(temp == '*')<br /> break; <br /> }<br /> while(scanf("%lf %lf",&x,&y)){<br /> if(x == 9999.9 && y == 9999.9)<br /> break;<br /> for(i=0;i<len;i++){ //test whether if point contained in any shap. if(s[i].kind == 'r' && x > s[i].x1 && x < s[i].x2 && y < s[i].y1 && y > s[i].y2){<br /> printf("Point %d is contained in figure %d\n",no,i+1);<br /> contain = true; <br /> }<br /> else if (s[i].kind == 'c' && (x-s[i].x1)*(x-s[i].x1)+(y-s[i].y1)*(y-s[i].y1) <br /> 　　　　　　　　　　< s[i].radius * s[i].radius){ printf("Point %d is contained in figure %d\n",no,i+1); contain = true; } else if (s[i].kind == 't'){ t0 = area(length(s[i].x1, s[i].y1, s[i].x2, s[i].y2), length(s[i].x1, s[i].y1, s[i].x3, s[i].y3), length(s[i].x2, s[i].y2, s[i].x3, s[i].y3)); t1 = area(length(x, y, s[i].x1, s[i].y1), length(x, y, s[i].x2, s[i].y2), length(s[i].x1, s[i].y1, s[i].x2, s[i].y2)); t2 = area(length(x, y, s[i].x1, s[i].y1), length(x, y, s[i].x3, s[i].y3), length(s[i].x1, s[i].y1, s[i].x3, s[i].y3)); t3 = area(length(x, y, s[i].x3, s[i].y3), length(x, y, s[i].x2, s[i].y2), length(s[i].x3, s[i].y3, s[i].x2, s[i].y2)); if(t1+t2+t3-t0 <= epsilon){ printf("Point %d is contained in figure %d\n",no,i+1); contain = true; } } } if(contain == false) printf("Point %d is not contained in any figure\n",no); no++; contain = false; } } double length(double x1, double y1, double x2, double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double area(double a, double b, double c){ double s = (a+b+c)/2; return sqrt(s*(s-a)*(s-b)*(s-c)); }