chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
近日,在中华英才网找工作的时候,看到如下一道笔试题: \N由用户输入四点坐标,请判断前三个坐标可否构成三角形;如果可以,则判断第四点坐标是否在三角形内(不含三边上,也不与三顶点重合)。可用任意语言编写程序。 \N呵,给大家两天时间,看谁做得好,最好的奖本论坛金币50、魅力10!(注意这是找工作时候的笔试题哦) \N两天后我将公布我用C++写的答案!
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2005-10-28 17:57(约18年前) |
|
|
chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
怎么没人顶一下?!
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2005-10-29 09:28(约18年前) |
|
|
chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
没人做吗? \N那要不要我把我的答案推迟贴出?
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2005-10-29 23:13(约18年前) |
|
|
Jeminai
自称:雙子騎士注册于:2005年5月26日 等级:站长 帖子数:6414 积分:41794 阅读权限:200 | |
呵呵,我会但我就不参与了。[em07] \N 我这个论坛比较开放,即便不注册也基本可以出入自由,所以论坛在线情况里客人要远多于会员、、、[em08]
|
我的Blog网址:blog.geminight.com |
|
| 发表于:2005-10-30 07:58(约18年前) |
|
|
chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
呵,大版主当然不用参与,参与了也没你的奖品,哈哈! \N现在把我用C++写的源码粘贴出来,谨供大家参考!至于源码中行缩进无法在贴子中正常显示的问题我就偷个懒不处理了,大家多花点心思慢慢看吧! \N#include <iostream.h> #include <math.h> \Nclass Point { public: double x; double y; }; \Nclass Triangle { private: Point vertexA; Point vertexB; Point vertexC; Point vertexD; public: Triangle() { vertexA.x=0; vertexA.y=0; vertexB.x=0; vertexB.y=0; vertexC.x=0; vertexC.y=0; vertexD.x=0; vertexD.y=0; } void SetA(Point vertex) { vertexA.x=vertex.x; vertexA.y=vertex.y; } void SetB(Point vertex) { vertexB.x=vertex.x; vertexB.y=vertex.y; } void SetC(Point vertex) { vertexC.x=vertex.x; vertexC.y=vertex.y; } void SetD(Point vertex) { vertexD.x=vertex.x; vertexD.y=vertex.y; } \N //判断三点可否构成三角形 bool IsTriangle() { //用几何学中的直线方程(两点式)判断 if(((vertexC.y-vertexA.y)*(vertexB.x-vertexA.x))!=(vertexC.x-vertexA.x)*(vertexB.y-vertexA.y)) return true; return false; } \N //******************************************* //判断第四点是否在三角形内 //******************************************* bool IsInside() { if(IsLineSegmentInside(vertexA,vertexB,vertexC)) { if(IsLineSegmentInside(vertexA,vertexC,vertexB)) return true; } return false; } \Nprivate: //******************************************************************* //判断一个顶点与第四点连成的直线,和该顶点的对边的交点是否在对边(线段)上 //******************************************************************* bool IsLineSegmentInside(Point vertexA,Point vertexB,Point vertexC) { double denominator,p1,p2,a1,a2,b1,b2; Point intersection; //用线性代数中的克拉默法则解方程组求两线交点 //直线方程(两点式)的线性方程通式是:(y1-y2)x+(x2-x1)y=x2*y1-x1*y2 //a1,a2,b1,b2分别是两个直线方程中x,y的系数,p1,p2则是两方程的常量 a1=vertexA.y-vertexB.y; //通式中的(y1-y2) a2=vertexC.y-vertexD.y; b1=vertexB.x-vertexA.x; //通式中的(x2-x1) b2=vertexD.x-vertexC.x; denominator=a1*b2-a2*b1; p1=vertexB.x*vertexA.y-vertexA.x*vertexB.y; p2=vertexD.x*vertexC.y-vertexC.x*vertexD.y; if(denominator!=0) { intersection.x=(p1*b2-p2*b1)/denominator; intersection.y=(a1*p2-a2*p1)/denominator; } //求出交点后,判断交点是否在边的线段上 double d1,d2,d; d=sqrt(pow((vertexB.x-vertexA.x),2)+pow((vertexB.y-vertexA.y),2)); d1=sqrt(pow((vertexB.x-intersection.x),2)+pow((vertexB.y-intersection.y),2)); d2=sqrt(pow((intersection.x-vertexA.x),2)+pow((intersection.y-vertexA.y),2)); if(d1>d || d2>d) return false; return true; } }; void main() { Triangle* triangle=new Triangle(); Point* vertex=new Point(); char m_continue='Y'; //do循环控制用户的重复计算需求 do { for(int i=1;i<=4;i++) { cout<<"Please input the "<<i<<" coordinates( total 4)"<<endl; cin>>vertex->x>>vertex->y; switch(i) { case 1: triangle->SetA(*vertex); break; case 2: triangle->SetB(*vertex); break; case 3: triangle->SetC(*vertex); break; case 4: triangle->SetD(*vertex); \N } } if(triangle->IsTriangle()) //判断是否可构成三角形 { cout<<"These three tops can constitute the triangle"<<endl; if(triangle->IsInside()) //判断第四点是否在三角形内 cout<<" and the fourth top is in the triangle"<<endl; else cout<<",but the fourth top is not in the triangle"<<endl; } else { cout<<"These three tops can't constitute the triangle"<<endl; } cout<<"Do you still need to go on to calculate other tops?(Y/N)"<<endl; cin>>m_continue; cout<<"\n\n\n"<<endl; }while(m_continue=='Y' || m_continue=='y'); }
\N这道题有很多种解法,但如何做到在题中尽可能的体现自己的功底就要看各人的修为了!哈,我也不知道自己做得好不好。
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2005-10-30 18:57(约18年前) |
|
|
chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
呵,这道题前一问很好解决,毕竟判断三点可否构成三角形的方法有很多,也很简单;重点应在后面那问,虽然也有多种方法可以解决,但逻辑的复杂度,代码的长短,算法用程序实现的复杂度等等都很考究,最后还要保证程序执行结果的完全正确。 \N本来我是想要用斜率来判断的,但后来才发现,这样会有很多“特殊情况”(如:直线与y轴平行时的斜率问题等等),为了解决这些特殊情况,不得不编上一大堆判断程序对它们做特殊处理;分析过后,我决定了用这样的方法(也就是上面源程序的方法): \N设前三点A、B、C可构成三角形(可从前面程序判断这点);则从三个顶点中任选两个分别与第四点确定两条直线,若这两条直线都分别和对边(线段,区别于线段外)相交,刚第四点在三角形内,否则在三角形外!用这个方法相对于其它方法而言,有两个好处:1、没有特殊情况;2、使用性线代数中的克拉默法则,算直线交点很简单。 \N好了,分析了这么多,不说了。下线。
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2005-10-30 22:28(约18年前) |
|
|
chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
就我一个人写了答案; \N呵,不会让我自己奖分给自己吧?
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2005-11-5 20:10(约18年前) |
|
|
Jeminai
自称:雙子騎士注册于:2005年5月26日 等级:站长 帖子数:6414 积分:41794 阅读权限:200 | |
真难为你了、、、[em19]
|
我的Blog网址:blog.geminight.com |
|
| 发表于:2005-11-5 20:37(约18年前) |
|
|
chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
哈,那是那是,我的那个苦啊!!! \N所以,大版主,有没有奖金发啊?
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2005-11-6 08:23(约18年前) |
|
|
Jeminai
自称:雙子騎士注册于:2005年5月26日 等级:站长 帖子数:6414 积分:41794 阅读权限:200 | |
奖励没有问题,不过奖金要建立在人气很旺的时候才有意义。 \N象你发这种参与度很强的帖子必须要有人才行(所以我从不发此类帖子[em08]),只有两个方法: \N1:到其他地方去宣传。 \N2:给程序区里的会员发email召唤,你可以看他们的信息里的邮箱地址(如:longgun,swsys,南斗)。[em27]
|
我的Blog网址:blog.geminight.com |
|
| 发表于:2005-11-6 10:13(约18年前) |
|
|
longgun
注册于:2005年9月18日 等级:注册会员 帖子数:25 积分:217 阅读权限:20 | |
楼主给出的代码很规范,似乎有开发经验?不像我写的代码,过一阵子连自己都看不明白了。
|
|
|
| 发表于:2005-12-17 13:21(约18年前) |
|
|
yy
注册于:2005年6月23日 等级:注册会员 帖子数:56 积分:490 阅读权限:20 | |
有没有更多有趣的题目啊
|
山不在高,有仙则灵;贴不在多,有偶则鸣 |
|
| 发表于:2006-1-17 22:13(约18年前) |
|
|
chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
以下是引用longgun在2005-12-17 13:21:00的发言: 楼主给出的代码很规范,似乎有开发经验?不像我写的代码,过一阵子连自己都看不明白了。 \N\N 谢谢你的称赞! \N从学写程序开始,小子就一直按通行的规范写程序。也许是长期积累的结果吧!
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2006-1-24 13:20(约18年前) |
|
|
chengen
注册于:2005年7月28日 等级:高级会员 帖子数:97 积分:1124 阅读权限:40 | |
以下是引用yy在2006-1-17 22:13:53的发言: 有没有更多有趣的题目啊 \N\N 有啊!呵呵,有机会多贴点!但你要来做啊! \N上次发的两个,很久很久都没人理我,差点郁闷死我了
|
Using codes to create beauty, that is my pride. |
|
| 发表于:2006-1-24 13:21(约18年前) |
|