Hi, please help me figure out where I went wrong.
problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=127
my code:
#include<bits/stdc++.h>
using namespace std;
struct point
{
int x,y;
};
struct line
{
point p1,p2;
};
//checks if point q lies on line segment pr.
bool onSegment(point p,point q,point r)
{
if(q.x<=max(p.x,r.x) && q.x>=min(p.x,r.x) && q.y<=max(p.y,r.y) && q.y>=min(p.y,r.y))
{
//cout<<p.x<<","<<p.y<<" "<<q.x<<","<<q.y<<" "<<r.x<<","<<r.y<<" lolololol"<<endl;
return true;
}
return false;
}
int turn(point p,point q,point r)
{
int result=(r.x-q.x)*(p.y-q.y)-(r.y-q.y)*(p.x-q.x);
if(result<0)return -1;//right
if(result>0)return 1;//left
return 0;//collinear
}
bool ccw(point p,point q,point r)
{
// cout<<"check "<<p.x<<","<<p.y<<" "<<q.x<<","<<q.y<<" "<<r.x<<","<<r.y<<"--> "<<turn(p,q,r)<<endl;
return turn(p,q,r) ;
}
bool intersection(line line1,line line2)
{
int o1=ccw(line1.p1,line1.p2,line2.p1);
int o2=ccw(line1.p1,line1.p2,line2.p2);
int o3=ccw(line2.p1,line2.p2,line1.p1);
int o4=ccw(line2.p1,line2.p2,line1.p2);
if( o1 != o2 && o3 != o4)
return 1;
//special cases
if(o1==0 && onSegment(line1.p1,line2.p1,line1.p2))
return true;
if(o2==0 && onSegment(line1.p1,line2.p2,line1.p2))
return true;
if(o3==0 && onSegment(line2.p1,line1.p1,line2.p2))
return true;
if(o4==0 && onSegment(line2.p1,line1.p2,line2.p2))
return true;
return false;
}
int main()
{
int n;
cin>>n;
while(n--)
{
point pp1,pp2,pp3,pp4,pp5,pp6;
cin>> pp5.x >>pp5.y >>pp6.x >>pp6.y;
cin>>pp1.x>>pp1.y>>pp3.x>>pp3.y;
if(pp1.x>pp3.x)
{
pp1.x^=pp3.x^=pp1.x^=pp3.x;
}
if(pp1.y<pp3.y)
{
pp1.y^=pp3.y^=pp1.y^=pp3.y;
}
if(pp5.x>=pp1.x && pp5.x<= pp3.x && pp5.y>=pp3.y && pp5.y <=pp1.y)
{
cout<<"T"<<endl;continue;
}
pp2.x=pp1.x;
pp2.y=pp3.y;
pp4.x=pp3.x;
pp4.y=pp1.y;
line l1,l2,l3,l4,l5;
l1.p1=pp1; l1.p2=pp2;
l2.p1=pp2; l2.p2=pp3;
l3.p1=pp3; l3.p2=pp4;
l4.p1=pp4; l4.p2=pp1;
l5.p1=pp5; l5.p2=pp6;
int result=intersection(l5,l1);
if(result)
{
cout<<"T"<<endl;
continue;
}
result=intersection(l5,l2);
if(result)
{
cout<<"T"<<endl;
continue;
}
result=intersection(l5,l3);
if(result)
{
cout<<"T"<<endl;
continue;
}
result=intersection(l5,l4);
if(result)
{
cout<<"T"<<endl;
continue;
}
cout<<"F"<<endl;
}
return 0;
}
For input
Correct output is,
T
your code productsF
.