It took me long time to get accepted. Needs some geometric knowledge, used graham scan algorithm, can be done also without using that, but most importantly made me crazy to figure out the special cases. So the coding was not well formatted. Adding some special input cases for the problem.
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>
#include <fstream>
#include <string>
#include <algorithm>
#define INF 1000000000
#define ll long long
using namespace std;
struct point{
int x,y;
};
struct line{
point p1,p2;
};
struct triangle{
point vertice[3];
};
vector<point> arr;
vector<int> II,JJ;
ll Area(point a,point b,point c)//b is the common point
{
ll val = (b.x-a.x)*(c.y-a.y) - (b.y-a.y) * (c.x-a.x);
return val;
}
ll _abs(ll a)
{
if(a<0)
return (-1)*a;
return a;
}
int mn(int aa,int bb)
{
if(aa<bb)
return aa;
return bb;
}
int mx(int aa,int bb)
{
if(aa>bb)
return aa;
return bb;
}
bool onLineSegment(point a,point c,point b)//c is on line ab
{
if(c.x<=mx(a.x,b.x) && c.x>=mn(a.x,b.x) && c.y<=mx(a.y,b.y) && c.y>=mn(a.y,b.y))
return 1;
return 0;
}
int findOrienation(point a,point b,point c)// line ac and check if point b is colinear,clockwise/anti-clockwise
{
//angle between two st.lines theta = (m1-m2)/1+m1*m2 ;
// from this we find (y3-y1)*(x2-x1)-(y2-y1)*(x3-x1);
//slope of ac =(c.y-a.y)/(c.x-a.x) slope of ab = (b.y-a.y)/(b.x-a.x)
// m1-m2 = (c.y-a.y)/(c.x-a.x) - (b.y-a.y)/(b.x-a.x)
//m1*m2 = (c.y-a.y)/(c.x-a.x)*(b.y-a.y)/(b.x-a.x)
ll val = (b.x-a.x)*(c.y-a.y) - (b.y-a.y) * (c.x-a.x);
if(val==0)//colinear
return 0;
if(val>0)
return 1;//anti-clockwise
return -1;//clockwise
}
bool doIntersectAnyEdge(triangle tr1,triangle tr2)
{
ll v1,v2,v3;
point a,b,c,d;
int f1,f2,f3,f4;
for(int i=0;i<3;i++)
{
a=tr1.vertice[i];
b=tr1.vertice[(i+1)%3];
for(int j=0;j<3;j++)
{
c = tr2.vertice[j];
d = tr2.vertice[(j+1)%3];
f1 = findOrienation(a,c,b);
f2 = findOrienation(a,d,b);
f3 = findOrienation(c,a,d);
f4 = findOrienation(c,b,d);
//cout<<f1<<" "<<f2<<" "<<f3<<" "<<f4<<"\n";
if(f1*f2==-1 && f3*f4==-1)
{
return 1;
}
}
}
return 0;
}
void doIntersectVertexNOTTOUCH(triangle t1,triangle t2)//not touch
{
point a,b,c;
for(int i=0;i<3;i++)
{
a = t1.vertice[i];
b = t1.vertice[(i+1)%3];
for(int j=0;j<3;j++)
{
c = t2.vertice[j];
if(c.x==a.x && c.y==a.y)
continue;
if(c.x==b.x && c.y==b.y)
continue;
if(findOrienation(a,c,b)==0 && onLineSegment(a,c,b)==1)
{
II.push_back(i);
JJ.push_back(j);
}
}
}
}
bool isEqual(point a,point b)
{
if(a.x==b.x && a.y==b.y)
return 1;
return 0;
}
ll area(int x1, int y1, int x2, int y2, int x3, int y3)
{
return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2)));
}
bool isInside(triangle tr,point a)
{
ll A = area(tr.vertice[0].x,tr.vertice[0].y, tr.vertice[1].x, tr.vertice[1].y, tr.vertice[2].x, tr.vertice[2].y);
ll A1 = area(tr.vertice[0].x,tr.vertice[0].y, tr.vertice[1].x, tr.vertice[1].y, a.x, a.y);
ll A2 = area(tr.vertice[0].x,tr.vertice[0].y, tr.vertice[2].x, tr.vertice[2].y, a.x, a.y);
ll A3 = area(tr.vertice[1].x,tr.vertice[1].y, tr.vertice[2].x, tr.vertice[2].y, a.x, a.y);
if(A != A1 + A2 + A3)
return 0;
for(int i=0;i<3;i++)
{
if(findOrienation(tr.vertice[i],a,tr.vertice[(i+1)%3])==0)
return 0;
}
return 1;
}
bool checkOrientation(triangle tr1,triangle tr2)
{
point a,b,c,d,e,f;
int pointsIndex[3]={0,0,0};
int cnt,idx;
for(int i=0;i<3;i++)
{
a = tr1.vertice[i];
b = tr1.vertice[(i+1)%3];
c = tr1.vertice[(i+2)%3];
int val = findOrienation(a,c,b);
cnt=0;
for(int j=0;j<3;j++)
{
d = tr2.vertice[j];
if(findOrienation(a,d,b)==0 && onLineSegment(a,d,b)==1 )
{
pointsIndex[j]=1;
cnt+=1;
}
}
if(cnt==2)
{
for(int k=0;k<3;k++)
{
if(pointsIndex[k]==0)
idx=k;
}
if(findOrienation(a,tr2.vertice[idx],b)==val)
return 1;
}
}
return 0;
}
bool isVertexOnEdge(triangle tr1,triangle tr2)
{
point a,b,c,d,e,f;
int cnt,idx,knt=0;
for(int i=0;i<3;i++)
{
a = tr1.vertice[i];
b = tr1.vertice[(i+1)%3];
cnt=0;
for(int j=0;j<3;j++)
{
d = tr2.vertice[j];
if((d.x==a.x && d.y==a.y) || (d.x==b.x && d.y==b.y) )
continue;
if(findOrienation(a,d,b)==0 && onLineSegment(a,d,b)==1 )
cnt+=1;
}
if(cnt>0)
{
knt+=1;
}
}
if(knt>=2)
return 1;
return 0;
}
int main()
{
int kase=1,t;
triangle tr1,tr2;
point a,b,c;
scanf("%d",&t);
line L1,L2;
bool FOUND;
//ofstream write;
//write.open("my_out.txt");
while(t--)
{
scanf("%d%d%d%d%d%d",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
tr1.vertice[0]=a;
tr1.vertice[1]=b;
tr1.vertice[2]=c;
scanf("%d%d%d%d%d%d",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
tr2.vertice[0]=a;
tr2.vertice[1]=b;
tr2.vertice[2]=c;
FOUND=0;
II.clear();JJ.clear();
//cout<<checkOrientation(tr1,tr2)<<"\n";
if(area(tr1.vertice[0].x,tr1.vertice[0].y,tr1.vertice[1].x,tr1.vertice[1].y,tr1.vertice[2].x,tr1.vertice[2].y)==0)
{
printf("pair %d: no\n",kase);
//write<<"pair "<<kase<<": no\n";
kase+=1;
continue;
}
if(area(tr2.vertice[0].x,tr2.vertice[0].y,tr2.vertice[1].x,tr2.vertice[1].y,tr2.vertice[2].x,tr2.vertice[2].y)==0)
{
printf("pair %d: no\n",kase);
//write<<"pair "<<kase<<": no\n";
kase+=1;
continue;
}
if(doIntersectAnyEdge(tr1,tr2)==1)
{
printf("pair %d: yes\n",kase);
//write<<"pair "<<kase<<": yes\n";
kase+=1;
continue;
}
//else
//{
doIntersectVertexNOTTOUCH(tr1,tr2);
if(II.size())
{
//check if this edge touches the opposite edge of jj of tr2 triangle
for(int ii=0;ii<II.size();ii++)
{
if(FOUND)
break;
point OppositEdgePoint1,OppositEdgePoint2;
int jj=JJ[ii];
if(jj==0)
{
OppositEdgePoint1 = tr2.vertice[1];
OppositEdgePoint2 = tr2.vertice[2];
}
else
{
OppositEdgePoint1 = tr2.vertice[(jj+1)%3];
OppositEdgePoint2 = tr2.vertice[jj-1];
}
if(findOrienation(OppositEdgePoint1,tr1.vertice[II[ii]],OppositEdgePoint2)==0)
{
if(isEqual(OppositEdgePoint1,tr1.vertice[II[ii]])==0 && isEqual(OppositEdgePoint2,tr1.vertice[II[ii]])==0)
{
FOUND=1;
//cout<<"here1\n";
}
}
if(findOrienation(OppositEdgePoint1,tr1.vertice[(II[ii]+1)%3],OppositEdgePoint2)==0)
{
if(isEqual(OppositEdgePoint1,tr1.vertice[(II[ii]+1)%3])==0 && isEqual(OppositEdgePoint2,tr1.vertice[(II[ii]+1)%3])==0)
{
FOUND=1;
//cout<<"here2\n";
}
}
}
}
if(FOUND)
{
printf("pair %d: yes\n",kase);
//write<<"pair "<<kase<<": yes\n";
kase+=1;
continue;
}
II.clear();
JJ.clear();
doIntersectVertexNOTTOUCH(tr2,tr1);
if(II.size())
{
//check if this edge touches the opposite edge of jj of tr1 triangle
for(int ii=0;ii<JJ.size();ii++)
{
if(FOUND)
break;
point OppositEdgePoint1,OppositEdgePoint2;
int jj=JJ[ii];
if(jj==0)
{
OppositEdgePoint1 = tr2.vertice[1];
OppositEdgePoint2 = tr2.vertice[2];
}
else
{
OppositEdgePoint1 = tr2.vertice[(jj+1)%3];
OppositEdgePoint2 = tr2.vertice[jj-1];
}
if(findOrienation(OppositEdgePoint1,tr1.vertice[II[ii]],OppositEdgePoint2)==0)
{
if(isEqual(OppositEdgePoint1,tr1.vertice[II[ii]])==0 && isEqual(OppositEdgePoint2,tr1.vertice[II[ii]])==0)
{
FOUND=1;
}
}
if(findOrienation(OppositEdgePoint1,tr1.vertice[(II[ii]+1)%3],OppositEdgePoint2)==0)
{
if(isEqual(OppositEdgePoint1,tr1.vertice[(II[ii]+1)%3])==0 && isEqual(OppositEdgePoint2,tr1.vertice[(II[ii]+1)%3])==0)
{
FOUND=1;
}
}
}
}
if(FOUND)
{
printf("pair %d: yes\n",kase);
//write<<"pair "<<kase<<": yes\n";
kase+=1;
continue;
}
for(int i=0;i<3;i++)
{
if(isInside(tr1,tr2.vertice[i]))
{
FOUND=1;
break;
}
if(isInside(tr2,tr1.vertice[i]))
{
FOUND=1;
break;
}
}
if(FOUND)
{
printf("pair %d: yes\n",kase);
//write<<"pair "<<kase<<": yes\n";
kase+=1;
continue;
}
//check if any two vertex of a triangle is on edge of other triangle and check their orientation
if(checkOrientation(tr1,tr2))
FOUND=1;
if(checkOrientation(tr2,tr1))
FOUND=1;
if(FOUND)
{
printf("pair %d: yes\n",kase);
//write<<"pair "<<kase<<": yes\n";
kase+=1;
continue;
}
if(isVertexOnEdge(tr1,tr2))
FOUND=1;
if(isVertexOnEdge(tr2,tr1))
FOUND=1;
if(FOUND)
{
printf("pair %d: yes\n",kase);
//write<<"pair "<<kase<<": yes\n";
kase+=1;
continue;
}
printf("pair %d: no\n",kase);
//write<<"pair "<<kase<<": no\n";
kase+=1;
}
//write.close();
return 0;
}
65 0 0 -2 -2 2 -2 -1 -1 1 -1 0 -2 0 0 -2 -2 4 -2 -1 -1 0 -2 2 -2 0 0 -2 -2 2 -2 0 0 -2 -2 2 -2 -2 4 0 4 0 2 0 0 2 0 0 2 0 2 -2 0 2 0 0 2 -1 1 1 1 2 9 -2 3 6 -5 0 6 -4 0 3 0 0 0 2 0 0 2 1 1 3 3 2 3 0 0 2 0 0 2 3 0 5 0 4 2 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 3 1 1 3 0 0 100 0 0 100 1 1 3 1 1 3 1 1 3 1 1 3 0 0 100 0 0 100 0 0 2 0 0 2 0 0 1 0 0 1 0 0 1 0 0 1 0 0 2 0 0 2 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 -1 0 0 -1 0 0 1 0 0 1 0 0 1 0 0 -1 0 0 2 0 0 2 1 1 3 3 2 3 0 0 2 0 0 2 3 0 5 0 4 2 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 3 1 1 3 0 0 100 0 0 100 1 1 3 1 1 3 1 1 3 1 1 3 0 0 100 0 0 100 0 0 2 0 0 2 0 0 1 0 0 1 0 0 1 0 0 1 0 0 2 0 0 2 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 -1 0 0 -1 0 0 5 0 2 4 4 0 5 0 -4 16 0 1 2 0 3 1 1 3 2 0 3 3 0 0 5 0 2 4 4 0 5 0 -4 16 -2 2 0 0 2 2 -2 -2 0 0 2 -2 -2 -2 0 0 2 -2 -2 2 0 0 2 2 0 0 -2 -2 2 -2 0 -1 2 2 -2 2 0 0 2 0 2 -2 0 0 -2 -2 2 -2 0 0 -4 -4 4 4 0 0 -1 -1 1 1 0 0 -4 -4 4 -4 0 0 -1 -1 1 -1 0 0 -4 -4 4 -4 0 0 -1 -1 1 1 0 0 -2 -2 2 -2 0 0 -2 2 3 10000 0 0 2 -2 -2 -2 0 -1 0 -1 0 -1 0 0 2 -2 -2 -2 0 -1 0 -1 0 -1 0 0 2 0 0 2 1 1 3 3 2 3 0 0 2 0 0 2 3 0 5 0 4 2 0 0 -2 -2 2 -2 0 6 -3 -3 3 -3 0 6 -3 -3 3 -3 0 0 -2 -2 2 -2 0 0 -2 -2 2 -2 1 -1 0 0 2 -2 0 0 -2 -2 2 -2 0 0 -2 -2 1 -1 0 0 -2 -2 2 -2 1 -1 2 -2 -2 -2 0 0 -2 -2 2 -2 5 19 -2 -2 2 -2 0 0 -2 -2 2 -2 5 19 -2 -2 10 -2 0 0 2 0 0 2 1 1 3 3 2 3 0 0 2 0 0 2 3 0 5 0 4 2 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 3 1 1 3 0 0 100 0 0 100 1 1 3 1 1 3 1 1 3 1 1 3 0 0 100 0 0 100 0 0 2 0 0 2 0 0 1 0 0 1 0 0 1 0 0 1 0 0 2 0 0 2 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 -1 0 0 -1 0 0 5 0 2 4 4 0 5 0 -4 16 0 1 2 0 3 1 1 3 2 0 3 3 0 0 0 4 4 0 0 4 -3 5 3 6 0 0 -2 -2 2 -2 -1 0 1 0 0 2 0 0 5 0 2 4 4 0 5 0 -4 16 0 0 2 0 0 2 3 0 5 0 4 2