题意： 给出两个三角形，要求输出两三角形的位置关系，是相交、相离还是包含，题意十分简单。
这道题最先碰到是在今年的三月份，那时候还没学过计算几何写了很垃圾的代码，把它贴在后面好了
// #include<bits/stdc++.h> #include<cstdio> #include<vector> #include<queue> #include<algorithm> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<iomanip> using namespace std; const double pi = acos((double)(-1)); #define inf 0x3f3f3f3f #define ll long long #define eps 1e-8 const int maxn = 1000010; const int mod = 1e9 + 7; int sgn(double x){ //判断x是否为0 if(fabs(x) < eps) return 0; else return x < 0?-1:1; } int dcmp(double x, double y){ //比较两个浮点数 if(fabs(x - y) < eps) return 0; else return x < y?-1:1; } struct Point{ double x,y; Point(){} Point(double x,double y):x(x),y(y){} Point operator + (Point B){return Point(x + B.x,y + B.y);} Point operator - (Point B){return Point(x - B.x,y - B.y);} Point operator * (double k){return Point(x*k,y*k);} Point operator / (double k){return Point(x/k,y/k);} bool operator == (Point B){return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;} bool operator < (const Point &b)const{ if(x == b.x) return y < b.y; return x < b.x; } }P[maxn]; Point ch[maxn]; typedef Point Vector; //用点的数据结构定义向量 struct Line{ Point p1,p2; Line(){} Line(Point p1,Point p2):p1(p1),p2(p2){} Line(Point p,double angle){ //y = kx + b p1 = p; if(sgn(angle - pi/2) == 0){p2 = (p1 + Point(0,1));} else {p2 = (p1 + Point(1,tan(angle)));} } Line(double a,double b,double c){ //ax + by + c = 0 if(sgn(a) == 0){ p1 = Point(0, -c/b); p2 = Point(1, -c/b); } else if(sgn(b) == 0){ p1 = Point(-c/a,0); p2 = Point(-c/a,1); } else{ p1 = Point(0,-c/b); p2 = Point(1,(-c - a)/b); } } }L[maxn]; typedef Line Segment; double Dist(Point A,Point B){ return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y)); } double Dot(Vector A,Vector B){return A.x*B.x + A.y*B.y;} //计算向量点积，>0锐角,<0钝角，=0直角 A·B = fabs(A)*fabs(B)*cos(angle) double Len(Vector A){return sqrt(Dot(A,A));} //计算向量长度 double Len2(Vector A){return Dot(A,A);} //向量长度的平方 double Angle(Vector A,Vector B){return acos(Dot(A,B)/Len(A)/Len(B));} //计算两向量的夹角 double Cross(Vector A,Vector B){return A.x*B.y - A.y*B.x;} //计算向量叉积，叉积有正负,A×B>0(B在A的逆时针方向),B×A<0 A×B = fabs(A)*fabs(B)*sin(angle) double Area(Vector A,Vector B,Vector C){return Cross(B- A,C - A);} //以A为公共点的两向量构成的平行四边形面积 Vector Rotate(Vector A,double rad){ //计算一个点逆时针选择rad度后的点 return Vector(A.x*cos(rad) - A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad)); } Vector Normal(Vector A){return Vector(-A.y/Len(A),A.x/Len(A));} //求该向量的法向量 bool Parallel(Vector A,Vector B){return sgn(Cross(A,B)) == 0;} //用叉积判断两向量是否平行或重合 int Point_line_relation(Point p, Line v){ //点和线的位置关系 int c = sgn(Cross(p - v.p1, v.p2 - v.p1)); if(c < 0) return 1; //p在v的左边(上面) if(c > 0) return 2; //p在v的右边(下面) return 0; } bool Point_on_seg(Point p, Line v){ //0为不在线段上，1为在线段上 return sgn(Cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(Dot(p - v.p1, p - v.p2)) <=0; } double Dis_point_line(Point p, Line v){ //点到直线的距离 return fabs(Cross(p - v.p1, v.p2 - v.p1))/Dist(v.p1, v.p2); } Point Point_line_proj(Point p, Line v){ //点在直线上的投影 double k = Dot(v.p2 - v.p1, p - v.p1)/Len2(v.p2 - v.p1); return v.p1 + (v.p2 - v.p1) * k; } Point Point_line_symmetry(Point p, Line v){ //点关于直线的对称点 Point q = Point_line_proj(p, v); return Point(2 * q.x - p.x, 2 * q.y - p.y); } double Dis_point_seg(Point p, Segment v){ //点到线段的距离 if(sgn(Dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(Dot(p - v.p2, v.p1 - v.p2)) < 0) return min(Dist(p, v.p1), Dist(p, v.p2)); return Dis_point_line(p, v); } int Line_relation(Line v1, Line v2){ //两条直线的位置关系 if(sgn(Cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0){ if(Point_line_relation(v1.p1, v2) == 0) return 1; //重合 else return 0; //平行 } return 2; //相交 } Point Cross_point(Point a, Point b, Point c, Point d){ //求两条直线的交点，Line1：ab，Line2：cd，两直线不平行不共线 double s1 = Cross(b - a, c - a); double s2 = Cross(b - a, d - a); return Point(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1); } bool Cross_segment(Point a, Point b, Point c, Point d){ //两线段是否规范相交 即如果一条线段的一个端点恰在另一条线段上则不视为相交；如果两条线段部分重合，也不视为相交。 double c1 = Cross(b - a, c - a), c2 = Cross(b - a, d - a); double d1 = Cross(d - c, a - c), d2 = Cross(d - c, b - c); return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0; //1：相交，0：不相交，端点重合不相交 } bool Cross_segment1(Point a, Point b, Point c, Point d){ //两线段是否非规范相交 return max(a.x, b.x) >= min(c.x, d.x)&& max(c.x, d.x) >= min(a.x, b.x)&& max(a.y, b.y) >= min(c.y, d.y)&& max(c.y, d.y) >= min(a.y, b.y)&& sgn(Cross(b - a, c - a)) * sgn(Cross(b - a, d - a)) <= 0&& sgn(Cross(d - c, a - c)) * sgn(Cross(d - c, b - c)) <= 0; sgn(Cross(c - b, a - b)) * sgn(Cross(d - b, a - b)) <= 0&& sgn(Cross(a - d, c - d)) * sgn(Cross(b - d, c - d)) <= 0; } double Helen(double a, double b, double c){ //海伦公式 double p = (a + b + c)/2; return sqrt(p * (p - a) * (p - b) * (p - c)); } int Point_in_polygon(Point pt, Point *p, int n){ //判断点和多边形的位置关系 for(int i = 0; i < n; i++){ if(p[i] == pt) return 3; //点在多边形的顶点上 } for(int i = 0; i < n; i++){ Line v = Line(p[i], p[(i + 1) % n]); if(Point_on_seg(pt, v)) return 2; //点在多边形边上 } int num = 0; for(int i = 0; i < n; i++){ int j = (i + 1) % n; int c = sgn(Cross(pt - p[j], p[i] - p[j])); int u = sgn(p[i].y - pt.y); int v = sgn(p[j].y - pt.y); if(c > 0 && u < 0 && v >= 0) num++; if(c < 0 && u >= 0 && v < 0) num--; } return num != 0; //1点在内部； 0点在外部 } double Polygon_area(Point *p, int n){ //求多边形面积 double area = 0; for (int i = 0; i < n; ++i) area += Cross(p[i], p[i + 1]); return area / 2; } Point Polygon_center(Point *p, int n){ //求多边形的重心 Point ans(0, 0); if(Polygon_area(p, n) == 0) return ans; for(int i = 0; i < n; i++) ans = ans + (p[i] + p[(i + 1) % n]) * Cross(p[i], p[(i + 1) % n]); return ans / Polygon_area(p, n) / 6; } int Andrew(int n){ //求凸包 sort(P, P + n); int len = 0; for(int i = 0; i < n; i++){ while(len > 1 && sgn(Cross(ch[len] - ch[len - 1], P[i] - ch[len - 1])) == -1) len--; ch[++len] = P[i]; } int k = len; for(int i = n - 2; i >= 0; i--){ while(len > k && sgn(Cross(ch[len] - ch[len - 1], P[i] - ch[len - 1])) == -1) len--; ch[++len] = P[i]; } return len; } int n, t; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>t; Point Pa[5], Pb[5]; while(t--){ for(int i = 0; i < 3; i++) cin>>Pa[i].x>>Pa[i].y; for(int i = 0; i < 3; i++) cin>>Pb[i].x>>Pb[i].y; L[1] = Line(Pa[0], Pa[1]); L[2] = Line(Pa[1], Pa[2]); L[3] = Line(Pa[2], Pa[0]); L[4] = Line(Pb[0], Pb[1]); L[5] = Line(Pb[1], Pb[2]); L[6] = Line(Pb[2], Pb[0]); int flag = 0, f1 = 1, f2 = 1; flag = 0; for(int i = 1; i <= 3; i++){ for(int j = 4; j <= 6; j++){ if(Cross_segment1(L[i].p1, L[i].p2, L[j].p1, L[j].p2)) flag = 1; } } if(flag){ cout<<"intersect"<<endl; continue; } for(int i = 0; i < 3; i++){ if(Point_in_polygon(Pa[i], Pb, 3) != 1) f1 = 0; if(Point_in_polygon(Pb[i], Pa, 3) != 1) f2 = 0; } if(f1 || f2) flag = 1; //包含 if(flag == 1) { cout<<"contain"<<endl; continue; } cout<<"disjoint"<<endl; } return 0; }今年三月份的代码
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<cmath> #define ll long long using namespace std; const int maxn=100010; const int mod=1000000007; int t; double x1,x2,x3,x4,x5,x6,y1,y2,y3,y4,y5,y6,s1,s2,p1,p2,a1,b1,c1,a2,b2,c2,max1,p,a,b,c,ss1,ss2,ss3,d1,d2,d3,d4; double distance(double x1,double x2,double y1,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double s(double a,double b,double c){ p=(a+b+c)/2.0; return sqrt(p*(p-a)*(p-b)*(p-c)); } double go(double x1,double y1,double x2,double y2,double x3,double y3){ a=distance(x1,x2,y1,y2); b=distance(x1,x3,y1,y3); c=distance(x2,x3,y2,y3); return s(a,b,c); } double xiangjiao(double x1,double y1,double x2,double y2,double x3,double y3){ return (x1-x3)*(y2-y3)-(y1-y3)*(x2-x3); } int main(){ cin>>t; while(t--){ cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4>>x5>>y5>>x6>>y6; a1=distance(x1,x2,y1,y2); b1=distance(x1,x3,y1,y3); c1=distance(x2,x3,y2,y3); a2=distance(x4,x5,y4,y5); b2=distance(x4,x6,y4,y6); c2=distance(x5,x6,y5,y6); p1=(a1+b1+c1)/2.0; p2=(a2+b2+c2)/2.0; s1=sqrt(p1*(p1-a1)*(p1-b1)*(p1-c1)); s2=sqrt(p2*(p2-a2)*(p2-b2)*(p2-c2)); int f=0,ff=0,f1=0,f2=0,f3=0,ff1=0,ff2=0,ff3=0,fff=0; d1=xiangjiao(x1,y1,x4,y4,x5,y5); d2=xiangjiao(x2,y2,x4,y4,x5,y5); d3=xiangjiao(x4,y4,x1,y1,x2,y2); d4=xiangjiao(x5,y5,x1,y1,x2,y2); if(d1*d2<=0&&d3*d4<=0) ff=1; d1=xiangjiao(x1,y1,x4,y4,x6,y6); d2=xiangjiao(x2,y2,x4,y4,x6,y6); d3=xiangjiao(x4,y4,x1,y1,x2,y2); d4=xiangjiao(x6,y6,x1,y1,x2,y2); if(d1*d2<=0&&d3*d4<=0) ff=1; d1=xiangjiao(x1,y1,x5,y5,x6,y6); d2=xiangjiao(x2,y2,x5,y5,x6,y6); d3=xiangjiao(x5,y5,x1,y1,x2,y2); d4=xiangjiao(x6,y6,x1,y1,x2,y2); if(d1*d2<=0&&d3*d4<=0) ff=1; d1=xiangjiao(x1,y1,x4,y4,x5,y5); d2=xiangjiao(x3,y3,x4,y4,x5,y5); d3=xiangjiao(x4,y4,x1,y1,x3,y3); d4=xiangjiao(x5,y5,x1,y1,x3,y3); if(d1*d2<=0&&d3*d4<=0) ff=1; d1=xiangjiao(x1,y1,x4,y4,x6,y6); d2=xiangjiao(x3,y3,x4,y4,x6,y6); d3=xiangjiao(x4,y4,x1,y1,x3,y3); d4=xiangjiao(x6,y6,x1,y1,x3,y3); if(d1*d2<=0&&d3*d4<=0) ff=1; d1=xiangjiao(x1,y1,x5,y5,x6,y6); d2=xiangjiao(x3,y3,x5,y5,x6,y6); d3=xiangjiao(x5,y5,x1,y1,x3,y3); d4=xiangjiao(x6,y6,x1,y1,x3,y3); if(d1*d2<=0&&d3*d4<=0) ff=1; d1=xiangjiao(x2,y2,x4,y4,x5,y5); d2=xiangjiao(x3,y3,x4,y4,x5,y5); d3=xiangjiao(x4,y4,x2,y2,x3,y3); d4=xiangjiao(x5,y5,x2,y2,x3,y3); if(d1*d2<=0&&d3*d4<=0) ff=1; d1=xiangjiao(x2,y2,x4,y4,x6,y6); d2=xiangjiao(x3,y3,x4,y4,x6,y6); d3=xiangjiao(x4,y4,x2,y2,x3,y3); d4=xiangjiao(x6,y6,x2,y2,x3,y3); if(d1*d2<=0&&d3*d4<=0) ff=1; d1=xiangjiao(x2,y2,x5,y5,x6,y6); d2=xiangjiao(x3,y3,x5,y5,x6,y6); d3=xiangjiao(x5,y5,x2,y2,x3,y3); d4=xiangjiao(x6,y6,x2,y2,x3,y3); if(d1*d2<=0&&d3*d4<=0) ff=1; if(ff==1){ puts("intersect"); continue; } ff=0; ss1=go(x1,y1,x2,y2,x4,y4); ss2=go(x1,y1,x3,y3,x4,y4); ss3=go(x3,y3,x2,y2,x4,y4); if(ss1+ss2+ss3<s1+1e-8) f1++; ss1=go(x1,y1,x2,y2,x5,y5); ss2=go(x1,y1,x3,y3,x5,y5); ss3=go(x3,y3,x2,y2,x5,y5); if(ss1+ss2+ss3<s1+1e-8) f2++; ss1=go(x1,y1,x2,y2,x6,y6); ss2=go(x1,y1,x3,y3,x6,y6); ss3=go(x3,y3,x2,y2,x6,y6); if(ss1+ss2+ss3<s1+1e-8) f3++; if(f1&&f2&&f3) f=1; f1=0,f2=0,f3=0; ss1=go(x4,y4,x5,y5,x1,y1); ss2=go(x4,y4,x6,y6,x1,y1); ss3=go(x6,y6,x5,y5,x1,y1); if(ss1+ss2+ss3<s2+1e-8) f1++; ss1=go(x4,y4,x5,y5,x2,y2); ss2=go(x4,y4,x6,y6,x2,y2); ss3=go(x6,y6,x5,y5,x2,y2); if(ss1+ss2+ss3<s2+1e-8) f2++; ss1=go(x4,y4,x5,y5,x3,y3); ss2=go(x4,y4,x6,y6,x3,y3); ss3=go(x6,y6,x5,y5,x3,y3); if(ss1+ss2+ss3<s2+1e-8) f3++; if(f1&&f2&&f3) f=1; if(f==1) puts("contain"); else puts("disjoint"); } }