191 - Intersection

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 191 WA , plizzzzzzzzzzzz help me

Try the I/O posted in this thread.
Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 191 WA , plizzzzzzzzzzzz help me

in the problem, it's specified that coordinates of the "top left" point and "bottom right" will be given. so isn't x(left) will always be smaller than x(right) and y(left) will always be greater than y(right)? i've solved the problem assuming this, and some of the I/O posted in the thread violates this assumption. so, is the specification not always correct and that's why getting WA?
Do or do not. There is no try.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 191 WA , plizzzzzzzzzzzz help me

The terms top left and bottom right do not imply any ordering of coordinates.
Check input and AC output for thousands of problems on uDebug!

naved92
New poster
Posts: 3
Joined: Thu Jul 05, 2012 1:10 pm

Re: 191 WA , plizzzzzzzzzzzz help me

can anyone help me finding the bug????

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;

class Point{

public:
int x,y;
void input(int a,int b);

};

void Point:: input(int a,int b)
{  x=a;
y=b;

return ;
}

int cross(Point pi,Point pj,Point pk)
{  int a,b;
//cout<<"calling cross"<<endl;
a=(pk.x-pi.x)*(pj.y-pi.y);
b=(pj.x-pi.x)*(pk.y-pi.y);
return a-b;

}

bool onsegment(Point pi,Point pj,Point pk)
{
int minx=min(pi.x,pj.x),maxx=max(pi.x,pj.x),miny=min(pi.y,pj.y),maxy=max(pi.y,pj.y);

if((minx<=pk.x) && (pk.x<=maxx) && (miny<=pk.y) && (pk.y<=maxy)) return true;
//cout<<minx<<maxx<<maxy<<miny;
//if(minx<=pk.x &(pk.x<=maxx) )return true;
else return false;

}
bool intersect(Point P1,Point P2,Point P3,Point P4)
{int d1,d2,d3,d4;
d1=cross(P3,P4,P1);
//cout<<"d1"<<d1<<endl;

d2=cross(P3,P4,P2);
//cout<<"d2"<<d2<<endl;

d3=cross(P1,P2,P3);
//cout<<"d3"<<d3<<endl;
d4=cross(P1,P2,P4);
//cout<<"d4"<<d4<<endl;
if((d1>0&&d2<0 || (d1<0&&d2>0) )&& ((d3>0&&d4<0)||(d3<0&&d4>0))) return true;
else if (d1==0 && onsegment(P3,P4,P1)) return true;
else if(d2==0 && onsegment(P3,P4,P2))return true;
else if(d3==0 && onsegment(P1,P2,P3))return true;
else if(d4==0 &&onsegment(P1,P2,P4))return true;
else return false;}

int main()
{  int tc,t=0;
cin>>tc;
while(tc--){
Point Ple,Pbe,P1,P2,P3,P4;
int xle,yle,xbe,ybe,xleft,ytop,xright,ybottom;
cin>>xle>>yle>>xbe>>ybe>>xleft>>ytop>>xright>>ybottom;

Ple.input(xle,yle);
Pbe.input(xbe,ybe);

P1.input(xleft,ytop);
P2.input(xleft,ybottom);
P3.input(xright,ybottom);
P4.input(xright,ytop);
if(intersect(Ple,Pbe,P1,P2)==true)cout<<"T"<<endl;
else if(intersect(Ple,Pbe,P2,P3)==true)cout<<"T"<<endl;
else if (intersect(Ple,Pbe,P3,P4)==true)cout<<"T"<<endl;
else if(intersect(Ple,Pbe,P4,P1)==true)cout<<"T"<<endl;
else cout<<"F"<<endl;
//cout<<"Case :"<<++t<<endl;
}

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 191 WA , plizzzzzzzzzzzz help me

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!

LifeMaker
New poster
Posts: 6
Joined: Sun Sep 19, 2010 11:28 pm

Re: 191 WA , plizzzzzzzzzzzz help me

The trick is that: "The rectangle consists of four straight lines and the area in between." so the line segment can intersect with a the area of the rectangle, and not necessarily intersect with the one of the sides of the rectangle.

so, for this test case:

Code: Select all

1
1 1 2 2 0 4 4 0
the ouput is

Code: Select all

T

RofaelEmil
New poster
Posts: 1
Joined: Tue Aug 07, 2012 5:54 pm

191 - Intersection

I took about an hour and 20 mins
in it
It got AC after replacing
every "<"/">" by "<="/">="
in lines 68-71
but I intended to do that as I see that there is no meaning for equality here
http://ideone.com/RZK9L
do you have any idea?
somebody tells me :"the point can be strictly on the rectangle"
but the previous four tests (Lines 40-66) surely got it
as the four previous conditions test intersection
and when we put "=" we mean intersection

Code: Select all

#include<iostream>
#include<complex>
using namespace std;

typedef complex<double> point;

#define vec(a,b) (b)-(a)
#define dot(a,b) (conj(a)*(b)).real()
#define cross(a,b) (conj(a)*(b)).imag()
#define lensqr(a) dot(a,a)
#define EPS 1e-9

double N, xstr, ystr, xend, yend, xtopLeft, ytopLeft, xbottomRight, ybottomRight;

bool Lines_intersect(const point &a, const point &b, const point &p, const point &q, point &ret) {
double d1 = cross(vec(a,p),vec(a,b)),
d2 = cross(vec(a,q),vec(a,b));
ret = (d1 * q - d2 * p) / (d1 - d2);
return fabs(d1 - d2) > EPS;
}

bool pointOnRay(const point &a, const point &b, const point &p) {
return cross(vec(a,b),vec(a,p)) < EPS
&& cross(vec(a,b),vec(a,p)) > -EPS
&& dot(vec(a,b),vec(a,p)) > -EPS;
}

bool pointOnSegment(const point &a, const point &b, const point &p) {
if (lensqr(vec(a,b)) < EPS)
return lensqr(vec(a,p)) < EPS;
return pointOnRay(a, b, p) && pointOnRay(b, a, p);
}

int main() {
cin >> N;
point ret;
while (N--) {
cin >> xstr >> ystr >> xend >> yend >> xtopLeft >> ytopLeft >> xbottomRight >> ybottomRight;

if (Lines_intersect(point(xstr, ystr), point(xend, yend), point(xtopLeft, ytopLeft), point(xtopLeft, ybottomRight), ret)
&& pointOnSegment(point(xstr, ystr), point(xend, yend), ret)
&& pointOnSegment(point(xtopLeft, ytopLeft), point(xtopLeft, ybottomRight), ret)) {
cout << "T" << endl;
continue;
}

if (Lines_intersect(point(xstr, ystr), point(xend, yend), point(xtopLeft, ytopLeft), point(xbottomRight, ytopLeft), ret)
&& pointOnSegment(point(xstr, ystr), point(xend, yend), ret)
&& pointOnSegment(point(xtopLeft, ytopLeft), point(xbottomRight, ytopLeft), ret)) {
cout << "T" << endl;
continue;
}

if (Lines_intersect(point(xstr, ystr), point(xend, yend), point(xbottomRight, ytopLeft), point(xbottomRight, ybottomRight), ret)
&& pointOnSegment(point(xstr, ystr), point(xend, yend), ret)
&& pointOnSegment(point(xbottomRight, ytopLeft), point(xbottomRight, ybottomRight), ret)) {
cout << "T" << endl;
continue;
}

if (Lines_intersect(point(xstr, ystr), point(xend, yend), point(xtopLeft, ybottomRight), point(xbottomRight, ybottomRight), ret)
&& pointOnSegment(point(xstr, ystr), point(xend, yend), ret)
&& pointOnSegment(point(xtopLeft, ybottomRight), point(xbottomRight, ybottomRight), ret)) {
cout << "T" << endl;
continue;
}

if (xstr <= (xtopLeft > xbottomRight ? xtopLeft : xbottomRight)
&& xstr >= (xtopLeft < xbottomRight ? xtopLeft : xbottomRight)
&& ystr <= (ytopLeft > ybottomRight ? ytopLeft : ybottomRight)
&& ystr >= (ytopLeft < ybottomRight ? ytopLeft : ybottomRight)) {
cout << "T" << endl;
continue;
}
cout << "F" << endl;
}
return 0;
}

shikhorroy
New poster
Posts: 27
Joined: Sat Jul 27, 2013 3:52 am

UVa - 191 Intersection(Getting WA)

Please escape me from this evil situation .....I'm getting WA again and again but can't find where is the problem....help me please.

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <climits>

#include <iostream>
#include<iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <sstream>
#include <algorithm>

using namespace std;

#define MAX 25
#define PI acos(-1.0)

typedef long long ll;
typedef pair <int, int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef map <string, int> msi;

#define REP(i, b, e)\
for(int i = int(b); i <= int(e); i++)
#define TRvi(c, it)\
for(vi::iterator it = (c).begin(); it != (c).end(); ++it )
#define TRvii(c, it)\
for(vii::iterator it = (c).begin(); it != (c).end(); ++it )
#define sf scanf
#define pf printf
#define si(x) sf("%d",&x)
#define in(x) cin>>x
#define out(x) cout<<(x)
#define ln length()
#define sz size()
#define clr clear()
#define pb push_back
#define mp make_pair
#define READ(f) freopen(f, "r", stdin)
#define mem(a,b) memset(a,b,sizeof(a))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define x first
#define y second

int area(ii p1, ii p2,ii p3)
{
int res = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y);
return (res == 0) ? 0 : (res > 0) ? 1 : -1;
}
bool onSigment(ii p1, ii p2,ii p3)
{
return (p3.x >= min(p1.x, p2.x) && p3.x <= max(p1.x, p2.x) && p3.y >= min(p1.y, p2.y) && p3.y <= max(p1.y, p2.y));
}
bool isInside_rect(int xstart, int ystart, int xend, int yend,  int xleft, int ytop, int xright, int ybottom)
{
return (xstart >= min(xleft, xright) && xstart <= max(xleft, xright) && ystart >= min(ybottom, ytop) && ystart <= max(ybottom, ytop) ||
xend >= min(xleft, xright) && xend <= max(xleft, xright) && yend >= min(ybottom, ytop) && yend <= max(ybottom, ytop)
);
}
bool isIntersect(ii lineA, ii lineB, ii rectX, ii rectY)
{
int abx = area(lineA, lineB, rectX);
int aby = area(lineA, lineB, rectY);

int xya = area(rectX, rectY, lineA);
int xyb = area(rectX, rectY, lineB);

if(xya == 0 && onSigment(rectX, rectY, lineA) ||
xyb == 0 && onSigment(rectX, rectY, lineB) ||
abx == 0 && onSigment(lineA, lineB, rectX) ||
aby == 0 && onSigment(lineA, lineB, rectY) ||
xya * xyb < 0 && abx * aby < 0
)
return true;
return false;
}

int main()
{
int n;
int xstart, ystart, xend, yend, xleft, ytop, xright, ybottom;
si(n);
while(n--)
{
sf("%d %d %d %d %d %d %d %d", &xstart, &ystart, &xend, &yend, &xleft, &ytop, &xright, &ybottom);

ii lineA = mp(xstart, ystart), lineB = mp(xend, yend);
ii rectW = mp(xleft, ytop), rectX = mp(xright, ytop), rectY = mp(xright, ybottom), rectZ = mp(xleft, ybottom);

if(isInside_rect(xstart, ystart, xend, yend, xleft, ytop, xright, ybottom))
{
pf("T\n");
continue;
}

if(isIntersect(lineA, lineB, rectW, rectX) || isIntersect(lineA, lineB, rectX, rectY) ||
isIntersect(lineA, lineB, rectY, rectZ) || isIntersect(lineA, lineB, rectZ, rectX))
pf("T\n");
else
pf("F\n");
}
return 0;
}

shikhorroy
New poster
Posts: 27
Joined: Sat Jul 27, 2013 3:52 am

Re: UVa - 191 Intersection(Getting WA)

yes!AC!... thewill
New poster
Posts: 6
Joined: Wed Dec 04, 2013 10:18 am

Re: UVa - 191 Intersection(Getting WA)

anybody plzz help...
how can the output for this prblm at the given input be false ...

0 18 8 12 1 1 11 11

as so the given points of rectangle would bee (1,1),(1,11),(11,1),(11,11) so the line obtained from first four points will have equation y=-0.75x +18 and the intersection point comes out to be (9.333,11) and (11,9.75) ,and both these points lie on the rectangle having lines y=11 and line x=11.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: UVa - 191 Intersection(Getting WA)

Your intersection points are not on the line segment.
Check input and AC output for thousands of problems on uDebug!

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 191 - Intersection

Can i assume the recangle lines are parallel to axis?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 191 - Intersection

Yes
(xleft, ytop) the top left and (xright, ybottom) the bottom right corner of the rectangle
Check input and AC output for thousands of problems on uDebug!

hiddenhopes
New poster
Posts: 4
Joined: Tue Aug 18, 2015 9:52 am

Re: 191-why getting wrong answer

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;

int direction(int xi,int yi, int xj,int yj, int xk,int yk){
return (xk-xi)*(yj-yi)-(xj-xi)*(yk-yi);
}

int intersect(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
int d1,d2,d3,d4,x;
d1=direction( x1, y1, x2, y2, x3, y3);
d2=direction( x1, y1, x2, y2, x4, y4);
d3=direction( x1, y1, x2, y2, x3, y4);
d4=direction( x1, y1, x2, y2, x4, y3);

if((d1>0&&d2>0&&d3>0&&d4>0)||(d1<0&&d2<0&&d3<0&&d4<0)) return 0;
else {

if(min(x3,x4)<=x1&&max(x3,x4)>=x1)
{if(min(y3,y4)<=y2&&max(y3,y4)>=y2) return 1;}

else if(min(x3,x4)<=x2&&max(x3,x4)>=x2)
{if(min(y3,y4)<=y1&&max(y3,y4)>=y1) return 1;}
else return 0;

}
}

int main(){

int t,x1,y1,x2,y2,rleft,rbottom,rright,rtop,check;

scanf("%d",&t);

while(t--){
scanf("%d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&rleft,&rtop,&rright,&rbottom);
check=intersect(x1,y1,x2,y2,rleft,rtop,rright,rbottom);
if(check) printf("T\n");
else printf("F\n");
}
return 0;
}
Last edited by brianfry713 on Wed Aug 19, 2015 8:45 pm, edited 1 time in total.
Reason: Added code block