首页 > 代码库 > P1355 神秘大三角
P1355 神秘大三角
题目描述
判断一个点与已知三角形的位置关系。
输入输出格式
输入格式：
前三行：每行一个坐标，表示该三角形的三个顶点
第四行：一个点的坐标，试判断该点与前三个点围成三角形的位置关系
(详见样例)
所有坐标值均为整数。
输出格式：
若点在三角形内（不含边界），输出1；
若点在三角形外（不含边界），输出2；
若点在三角形边界上（不含顶点），输出3；
若点在三角形顶点上，输出4。
输入输出样例
输入样例#1：
(0,0)(3,0)(0,3)(1,1)
输出样例#1：
1
说明
【数据规模与约定】
对于100%数据，0<=所有点的横、纵坐标<=100
本题数据较弱，怎公搞都可以A。就当练练思路吧。
//自己脑洞的AC代码 #include<cstdio>#include<cmath>using namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const double Pi=acos(-1);struct node{ int x,y; bool operator ==(const node &a){ return x==a.x&&y==a.y; }}A,B,C,D;void init(){ A.x=read();A.y=read(); B.x=read();B.y=read(); C.x=read();C.y=read(); D.x=read();D.y=read();}double slop(node a,node b){ if(a.x==b.x) return 1e9; return (double)(a.y-b.y)/(double)(a.x-b.x);}bool deal(node a,node b){//精度要求较高 node t1,t2; t1.x=a.x-D.x;t1.y=a.y-D.y; t2.x=b.x-D.x;t2.y=b.y-D.y; double xiang=(double)(t1.x*t2.x+t1.y*t2.y); double mo=sqrt((t1.x*t1.x+t1.y*t1.y)*(t2.x*t2.x+t2.y*t2.y)); double cita=xiang/mo; if(acos(cita)==Pi) return 1; else return 0;}void work(){ if(D==A||D==B||D==C){puts("4");return ;} //点积求角 180则共线 if(deal(A,B)){puts("3");return ;} if(deal(A,C)){puts("3");return ;} if(deal(B,C)){puts("3");return ;} //判断点是否在三角形中 //http://files.cnblogs.com/files/shenben/%E5%88%A4%E6%96%AD%E7%82%B9%E6%98%AF%E5%90%A6%E5%9C%A8%E4%B8%89%E8%A7%92%E5%BD%A2%E4%B8%AD.sh if(slop(A,B)!=slop(A,C)&&slop(A,D)!=slop(B,C) &&(slop(A,D)-slop(A,B))*(A.x-B.x)*(slop(A,D)-slop(A,C))*(A.x-C.x)<=0 &&(slop(A,D)-slop(B,C))*(A.x-D.x)*(slop(B,D)-slop(B,C))*(B.x-D.x)<0){ puts("1"); } else puts("2");}int main(){ init(); work(); return 0;}
//题解更好思路的AC代码 #include<cstdio>#include<cstdlib>#include<cmath>using namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}struct node{ int x,y; bool operator ==(const node &a){ return x==a.x&&y==a.y; }}A,B,C,D;void init(){ A.x=read();A.y=read(); B.x=read();B.y=read(); C.x=read();C.y=read(); D.x=read();D.y=read();}int calc(const node &a,const node &b,const node &c){//cross product return abs((a.x*b.y+b.x*c.y+c.x*a.y)-(a.x*c.y+b.x*a.y+c.x*b.y));}void work(){ if(D==A||D==B||D==C) puts("4"); else{//精度要求较低 if(calc(D,A,B)+calc(D,A,C)+calc(D,B,C)!=calc(A,B,C)) puts("2");//面积不等，必在三角形外 else if(!calc(D,A,B)||!calc(D,A,C)||!calc(D,B,C)) puts("3");//叉积=0，就在线段上(不严谨..) else puts("1");//只剩下在三角形内 } }int main(){ init(); work(); return 0;}
P1355 神秘大三角
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。