判断一个点与已知三角形的位置关系。
前三行：每行一个坐标，表示该三角形的三个顶点
第四行：一个点的坐标，试判断该点与前三个点围成三角形的位置关系
(详见样例)
所有坐标值均为整数。
输出格式：
若点在三角形内（不含边界），输出1；
若点在三角形外（不含边界），输出2；
若点在三角形边界上（不含顶点），输出3；
若点在三角形顶点上，输出4。
(0,0) (3,0) (0,3) (1,1)
1
【数据规模与约定】
对于100%数据，0<=所有点的横、纵坐标<=100
//自己脑洞的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; }
原文：http://www.cnblogs.com/shenben/p/6282803.html