FZU - 2273 Triangles(计算几何)
程序员文章站
2022-04-01 16:11:23
...
Triangles
题意: 给出两个三角形,要求输出两三角形的位置关系,是相交、相离还是包含,题意十分简单。
这道题最先碰到是在今年的三月份,那时候还没学过计算几何写了很垃圾的代码,把它贴在后面好了
// #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");
}
}