191 - Intersection

[visser]

Try your program on

1
0 2 0 3 0 0 1 1

Output should be 'F'!

[Moni]

Hey!
I am confused ! What this thing really mean ?

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

Can anybody explain ?

[bjacoke001]

It just means that the two points will be opposite corners of the rectangle, but aren't necessarily the top left and bottom right points. All you have to do is add a couple if statements to make the points the top left and bottom right corners, or you can just leave them as they are because their position doesn't really matter (in my solution at least).

[rakeb]

Here is my code. i don't know why it gets wa. can anybody help?
[c]
#include <stdio.h>

#define left 1
#define right -1
#define colen 0

struct D
{
int x,y;

};

int orien(D a,D b,D c)
{
int z;
z=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
if(z > 0)
return left;
if(z < 0)
return right;
return colen;
}

int between(D a,D b,D c)
{
if(a.x < b.x)
return (a.x <= c.x && c.x <= b.x);

else if(a.x > b.x)
return (b.x <= c.x && c.x <= a.x);

else if(a.y < b.y)
return (a.y <= c.y && c.y <= b.y);
else
return (b.y <= c.y && c.y <= a.y);
}

int intersect(D a,D b,D c,D d)
{
int abc,abd;
abc = orien(a,b,c);
abd = orien(a,b,d);

if(abc != abd)
return (orien(c,d,a) != orien(c,d,b));
else
return (abc==colen && (between(a,b,c) || between(a,b,d) ||between(c,d,a)));
}

int inside(D a,D b,D c,D d,D e,D f)
{
if((a.x <= e.x) && (d.x >= e.x) && a.x <= f.x && d.x >= f.x)
return ((a.y >= e.y && b.y <= e.y) && ( a.y >= f.y && b.y <= f.y ));
return 0;
}

void main()
{
D a,b,c,d,e,f;
int n;
//freopen("191.in","r",stdin);
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d%d%d%d%d%d",&e.x,&e.y,&f.x,&f.y,&a.x,&a.y,&c.x,&c.y);
b.x = a.x;
b.y = c.y;
d.x = c.x;
d.y = a.y;

if(a.y==c.y || a.x==c.x) //if rectangle is a line
{
if(intersect(a,c,e,f))
{
printf("T\n");
continue;
}
else
{
printf("F\n");
continue;
}
}

//if right-top and left-bottom of rectangle is given
if (a.y<c.y)
{
if(inside(b,a,d,c,e,f))
{
printf("T\n");
continue;

}
}
else
{
if(inside(a,b,c,d,e,f))
{
printf("T\n");
continue;
}
}


if(intersect(a,b,e,f))
printf("T\n");
else if(intersect(b,c,e,f))
printf("T\n");
else if(intersect(c,d,e,f))
printf("T\n");
else if(intersect(a,d,e,f))
printf("T\n");
else
printf("F\n");
}
}
[/c]

[prilmeie]

Hello folks,

I am having problems with the OJ C++ compiler. The program below compiles perfectly with the free Borland C++ compiler (Version 5.5.1) and with the GNU g++ compiler version 3.2, but the judge rejects it with a compile error.

The compiler error messages seem strange to me:
01314075_24.c: In method `bool LineSegment::intersects (const
LineSegment &) const':
01314075_24.c:71: `full' undeclared (first use this function)
01314075_24.c:71: (Each undeclared identifier is reported only once for
each function it appears in.)
01314075_24.c:71: parse error before `int'
01314075_24.c:75: `a11' undeclared (first use this function)
01314075_24.c `intersection' undeclared (first use this function)
01314075_24.c parse error before `distance'
01314075_24.c:110: `intersectionX' undeclared (first use this function)
01314075_24.c: In method `Rectangle::Rectangle (int, int, int, int)':
01314075_24.c:157: `what' undeclared (first use this function)
01314075_24.c:157: parse error before `means'
01314075_24.c: At top level:
01314075_24.c:162: parse error at end of saved function text

Can someone explain me what's going on here? The error message mentions several identifiers I never declared.

regards,
Franz

[cpp]
/* @JUDGE_ID: my_id 191 C++ "Linear Algebra" */

#include <iostream>
#include <cmath>

inline double sqr( const double x )
{
return x * x;
}

void swap( int * const a, int * const b )
{
int temp = *a;
*a = *b;
*b = temp;
}

inline double distance( const double fromX, const double fromY, const double toX, const double toY )
{
return std::sqrt( sqr( fromX - toX ) + sqr( fromY - toY ) );
}

class Point
{
private:
const int _x;
const int _y;

public:
Point( const int x, const int y ) : _x( x ), _y( y ) {}

const int getX() const
{
return this->_x;
}

const int getY() const
{
return this->_y;
}
};

class LineSegment
{
private:
int _startx, _starty;
int _endx, _endy;
double _distance;

public:
LineSegment( const int startx, const int starty, const int endx, const int endy )
: _startx( startx ), _starty( starty ), _endx( endx ), _endy( endy ),
_distance( distance( static_cast<double>( startx ), static_cast<double>( starty ), static_cast<double>( endx ), static_cast<double>( endy) ) )
{
// normalize: line goes from left to right:
if ( startx > endx ) {
swap( &_startx, &_endx );
swap( &_starty, &_endy );
}
}

bool intersects( const LineSegment & other ) const
{
// Check if both lines segments intersect if they where full lines
int a11 = this->_endx - this->_startx;
int a12 = other._endx - other._startx;
int a21 = this->_endy - this->_starty;
int a22 = other._endy - other._starty;
int determinant = a11 * a22 - a12 * a21;

if ( determinant != 0 ) {
double inverse11 = static_cast<double>( a22 ) / static_cast<double>( determinant );
double inverse12 = static_cast<double>(-a12 ) / static_cast<double>( determinant );
double inverse21 = static_cast<double>(-a21 ) / static_cast<double>( determinant );
double inverse22 = static_cast<double>( a11 ) / static_cast<double>( determinant );

double x1 = inverse11 * static_cast<double>( other._startx - this->_startx )
+ inverse12 * static_cast<double>( other._starty - this->_starty );

double x2 = inverse21 * static_cast<double>( other._startx - this->_startx )
+ inverse22 * static_cast<double>( other._starty - this->_starty );

// Both are line segments, so the calculated intersection point
// must be on the segments and not outside, the distance between the
// intersection point and the edges of the line segment must be
// smaller than the distance between the two edges.
double intersectionX = this->_startx + x1 * ( this->_endx - this->_startx );
double intersectionY = this->_starty + x1 * ( this->_endy - this->_starty );

double dist1 = distance( this->_startx, this->_starty, intersectionX, intersectionY );
double dist2 = distance( this->_endx, this->_endy, intersectionX, intersectionY );
double dist3 = distance( other._startx, other._starty, intersectionX, intersectionY );
double dist4 = distance( other._endx, other._endy, intersectionX, intersectionY );

if ( dist1 > this->_distance || dist2 > this->_distance ) {
return false;
}

if ( dist3 > other._distance || dist4 > other._distance ) {
return false;
}

return true;
}
return false;
}

Point getStartPoint() const
{
return Point( this->_startx, this->_starty );
}

Point getEndPoint() const
{
return Point( this->_endx, this->_endy );
}
};

class Rectangle
{
private:
int _xleft;
int _ybottom;
int _xright;
int _ytop;

public:
Rectangle( const int xleft, const int ybottom, const int xright, const int ytop )
: _xleft( xleft ), _ybottom( ybottom ), _xright( xright ), _ytop( ytop )
{
// It is guaranteed that xleft ybottom actually is that what it means:
if ( xright < xleft ) {
swap( &_xright, &_xright );
}

if ( ytop < ybottom ) {
swap( &_ytop, &_ybottom );
}
}

bool contains( const LineSegment & s ) const
{
Point p1 = s.getStartPoint();

if ( (p1.getX() >= this->_xleft && p1.getX() <= this->_xright) &&
(p1.getY() >= this->_ybottom && p1.getY() <= this->_ytop) ) {
return true;
}

Point p2 = s.getEndPoint();

if ( (p2.getX() >= this->_xleft && p2.getX() <= this->_xright) &&
(p2.getY() >= this->_ybottom && p2.getY() <= this->_ytop) ) {
return true;
}

return false;
}

bool intersects( const LineSegment & with ) const
{
LineSegment a( this->_xleft, this->_ybottom, this->_xright, this->_ybottom );

if ( with.intersects( a ) == true ) {
return true;
}

LineSegment b( this->_xleft, this->_ytop, this->_xright, this->_ytop );

if ( with.intersects( b ) == true ) {
return true;
}

LineSegment c( this->_xright, this->_ytop, this->_xright, this->_ybottom );

if ( with.intersects( c ) == true ) {
return true;
}

LineSegment d( this->_xleft, this->_ytop, this->_xleft, this->_ybottom );

if ( with.intersects( d ) == true ) {
return true;
}

return false;
}
};

int main()
{
int n;

std::cin >> n;

for ( int i = 0; i < n; ++i ) {
// The line:
int startx, starty, endx, endy;
std::cin >> startx >> starty >> endx >> endy;

LineSegment e( startx, starty, endx, endy );

// The rectangle:
int xleft, ytop, xright, ybottom;
std::cin >> xleft >> ybottom >> xright >> ytop;

Rectangle r( xleft, ybottom, xright, ytop );

if ( r.contains(e) || r.intersects(e) ) {
std::cout << 'T' << std::endl;
} else {
std::cout << 'F' << std::endl;
}
}

return 0;
}
[/cpp]

[Caesum]

sounds like a line wrap error in your email client (outlook express ?). Set it to wrap lines at a greater number of characters or shorten your lines.

eg 'full' is part of one of your comments but probably appears wrapped to a new line because the line is long.

[Jordan Gordeev]

You have submitting problem. I guess you are using e-mail submission. Do you see the long one-line comment containing the word full? SMTP servers (the servers delivering electronic mail) and many e-mail clients love wrapping long lines, so what the judge receives is:
// Check if both lines segments intersect if they where
full lines

and you see that the second line is not a comment.
I recomment you using a C-style comment (/* ... */)

[prilmeie]

You have submitting problem. [...] I recomment you using a C-style comment (/* ... */)

You are right, this has been a submitting problem. I am using Mozilla which autowraped lines and C++ comments. Although this program produces WA it now compiles.

Thanks,
Franz

[haquin]

I have a wrong answer for the problem 191 and all the test in the forum work. Can anybody help me ??

[hank]

Here are some testdata.
input:

Code: Select all

68
4 9 11 2 1 1 7 5
11 2 4 9 1 1 7 5
12 12 24 24 19 5 25 17
4 6 15 9 1 1 11 11
19 5 25 17 12 12 24 24
0 18 8 12 1 1 11 11
2 4 4 2 1 1 11 11
-4 9 -11 2 -1 1 -7 5
-11 2 -4 9 -1 1 -7 5
-12 12 -24 24 -19 5 -25 17
-4 6 -15 9 -1 1 -11 11
-19 5 -25 17 -12 12 -24 24
0 18 -8 12 -1 1 -11 11
-2 4 -4 2 -1 1 -11 11
4 -9 11 -2 1 -1 7 -5
11 -2 4 -9 1 -1 7 -5
12 -12 24 -24 19 -5 25 -17
4 -6 15 -9 1 -1 11 -11
19 -5 25 -17 12 -12 24 -24
0 -18 8 -12 1 -1 11 -11
2 -4 4 -2 1 -1 11 -11
-4 -9 -11 -2 -1 -1 -7 -5
-11 -2 -4 -9 -1 -1 -7 -5
-12 -12 -24 -24 -19 -5 -25 -17
-4 -6 -15 -9 -1 -1 -11 -11
-19 -5 -25 -17 -12 -12 -24 -24
0 -18 -8 -12 -1 -1 -11 -11
-2 -4 -4 -2 -1 -1 -11 -11
9 1 9 2 4 3 9 6
9 2 9 1 4 3 9 6
10 3 13 3 4 3 9 6
13 3 10 3 4 3 9 6
10 6 14 6 4 3 9 6
14 6 10 6 4 3 9 6
9 7 9 10 4 3 9 6
9 10 9 7 4 3 9 6
4 7 4 10 4 3 9 6
4 10 4 7 4 3 9 6
0 6 3 6 4 3 9 6
3 6 0 6 4 3 9 6
1 3 3 3 4 3 9 6
3 3 1 3 4 3 9 6
4 0 4 2 4 3 9 6
4 2 4 0 4 3 9 6
5 3 8 5 4 3 9 6
8 5 5 3 4 3 9 6
5 3 8 3 4 3 9 6
8 3 5 3 4 3 9 6
6 4 6 5 4 3 9 6
6 5 6 4 4 3 9 6
4 3 9 6 4 3 9 6
9 6 4 3 4 3 9 6
4 3 5 4 4 3 9 6
5 4 4 3 4 3 9 6
5 3 8 3 4 3 9 6
8 3 5 3 4 3 9 6
5 3 9 3 4 3 9 6
9 3 5 3 4 3 9 6
4 4 4 5 4 3 9 6
4 5 4 4 4 3 9 6
4 3 4 5 4 3 9 6
4 5 4 3 4 3 9 6
4 3 4 6 4 3 9 6
4 6 4 3 4 3 9 6
9 2 9 5 4 3 9 6
9 5 9 2 4 3 9 6
9 2 9 7 4 3 9 6
9 7 9 2 4 3 9 6

[hank]

output:

Code: Select all

F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T

good luck~

[haquin]

Thanks a lot. I didn't understand that "xstart" could be larger than "xend"

sorry for my english

[Eric]

What did you discover?
I am trying to solve this problem but have no idea.

[Partha]

Book name: "Algorithm in C++"
Writer : Robert Sedgewick

See page no. 349. I think this is one of the most efficient algorithm about Line Segment Intersection and the best way of solve this problem.

[Cool Guyz]

can someone find me the mistakes plsss
[c]
#include <stdio.h>

void main()
{ float xs,ys,xe,ye,xl,yt,xr,yb,xp,yp,i,n,x,y,p;
scanf("%f",&n);
for (i=0;i<n;i++)
{ y=x=yp=xp=0;
scanf("%f %f %f %f %f %f %f %f",&xs,&ys,&xe,&ye,&xl,&yt,&xr,&yb);
if (xl>xr) { p=xl;xl=xr;xr=p; }
if (yb>yt) { p=yb;yb=yt;yt=p; }
if (yt>=ye && yt<=ys || yt>=ys && yt<=ye) yp=yt;
else if (yb>=ye && yb<=ys || yb>=ys && yb<=ye) yp=yb;
if (xr>=xs && xr<=xe || xr>=xe && xr<=xs) xp=xr;
else if (xl>=xs && xl<=xe || xl>=xe && xl<=xs) xp=xl;
if (yp!=yt && yp!=yb && xp!=xl && xp!=xr) { printf("F\n"); continue; }
if (xp==xl || xp==xr)
{ if (xe-xs==0) y=ys;
else y=(xp-xs)*(ye-ys)/(xe-xs)+ys;
}
else y=yb-1;
if (yp==yb || yp==yt)
{ if (ye-ys==0) x=xs;
else x=(xe-xs)*(yp-ys)/(ye-ys)+xs;
}
else x=xl-1;
if (x>=xl && x<=xr) printf("T\n");
else if (y>=yb && y<=yt) printf("T\n");
else printf("F\n");
}
}[/c]