191 - Intersection

[brianfry713]

Try the I/O posted in this thread.

[Scarecrow]

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?

[brianfry713]

The terms top left and bottom right do not imply any ordering of coordinates.

[naved92]

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]

Try the I/O in this thread.

[LifeMaker]

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]

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]

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()
{
//    READ("input.txt");
    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]

yes!AC!...

[thewill]

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]

Your intersection points are not on the line segment.

[Farsan]

Can i assume the recangle lines are parallel to axis?

[brianfry713]

Yes
(xleft, ytop) the top left and (xright, ybottom) the bottom right corner of the rectangle

[hiddenhopes]

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;
}