<分区>
问题:
给定两个三角形的顶点，检查它们是否有公共(public)内点。边或顶点上的任何点都不会被视为三角形的内部。
我认为这是一个判断两个三角形是否相交的问题。
我的想法是:
1. Make three line segments for each of the two triangles
2. For each pair of line segment (A,B) (where A is in triangle #1 and B is in Triangle #2) check whether they intersect or not.
3. If any pair of segments intersect, then the two triangles have a interior point. Otherwise not .
我的代码:
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#define READ freopen("in.txt","r",stdin)
#define ui64 unsigned long long int
#define i64 long long int
using namespace std;
class Point{
public:
i64 x, y;
Point() : x(0), y(0) {}
Point(int a, i64 b) : x(a), y(b) {}
};
class Segment{
public:
Point a, b;
Segment() : a(0,0), b(0,0) {}
Segment(Point e, Point r) : a(e), b(r) {}
Segment(const Segment &s){
a = s.a;
b = s.b;
}
i64 Direction(const Point &p){
return (p.x - a.x) * (b.y - a.y) - (b.x - a.x) * (p.y - a.y);
}
inline bool inside(int a,int b,int c){
return a<=c && c<=b;
}
bool onSegment(const Point &p){
return inside(min(a.x,b.x), max(a.x,b.x), p.x) && inside(min(a.y,b.y), max(a.y,b.y), p.y);
}
bool Intersect(Segment &s){
int d1 = this->Direction(s.a);
int d2 = this->Direction(s.b);
int d3 = s.Direction(a);
int d4 = s.Direction(b);
if(((d1>0 && d2<0) || (d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))) return true;
//check if the two segments just touch each other but don't cross
//i ignored this because as the problem said ...
//No points on the edges or vertices are considered interior to a triangle.
/*if(!d1 && this->onSegment(s.a)) return true;
if(!d2 && this->onSegment(s.b)) return true;
if(!d3 && s.onSegment(a)) return true;
if(!d4 && s.onSegment(b)) return true;*/
return false;
}
};
Point p1[3], p2[3];
Segment s1[3], s2[3];
bool check()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(s1[i].Intersect(s2[j]))
return true;
return false;
}
int main()
{
//READ;
int t, ts=0;
scanf("%d",&t);//number of test cases
while(t--){
//points for first triangle
for(int i=0;i<3;i++){
scanf("%lld %lld",&p1[i].x, &p1[i].y);
}
//points for second triangle
for(int i=0;i<3;i++){
scanf("%lld %lld",&p2[i].x, &p2[i].y);
}
for(int i=0;i<3;i++){
s1[i] = Segment(p1[i], p1[(i+1)%3]);
s2[i] = Segment(p2[i], p2[(i+1)%3]);
}
printf("pair %d: %s\n",++ts, check() ? "yes" : "no");
}
return 0;
}
但是对于这个输入..
1
0 0 5 0 2 4
4 0 5 0 -4 16
我的程序给出了输出
no
但正确答案是
yes
而且在很多情况下我的程序无法正常工作。
我检查了我的 Segment 类是否有其他程序，它工作正常。
但是在这，我找不到错误。
请帮忙。
谢谢。