## 191 - Intersection

Moderator: Board moderators

visser
New poster
Posts: 8
Joined: Mon Jun 10, 2002 11:13 am
Location: Netherlands

1
0 2 0 3 0 0 1 1

Output should be 'F'!

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

### Hmm! 191

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 ? We are all in a circular way, no advances, only moving and moving!

bjacoke001
New poster
Posts: 6
Joined: Fri Jul 26, 2002 6:42 pm
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
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

### 191 Intersection Why WA? plz give me some test data

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]
Rakeb

prilmeie
New poster
Posts: 13
Joined: Fri Jan 03, 2003 2:21 pm
Location: Germany
Contact:

### Weird compile error

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
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
New poster
Posts: 14
Joined: Tue Nov 12, 2002 6:04 pm
Location: Bulgaria
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
New poster
Posts: 13
Joined: Fri Jan 03, 2003 2:21 pm
Location: Germany
Contact:
Jordan Gordeev wrote: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
New poster
Posts: 2
Joined: Fri Feb 07, 2003 6:11 pm

I have a wrong answer for the problem 191 and all the test in the forum work. Can anybody help me ??
Last edited by haquin on Tue Feb 11, 2003 4:18 pm, edited 1 time in total.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
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
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
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
New poster
Posts: 2
Joined: Fri Feb 07, 2003 6:11 pm
Thanks a lot. I didn't understand that "xstart" could be larger than "xend" sorry for my english

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
What did you discover?
I am trying to solve this problem but have no idea.

Partha
New poster
Posts: 5
Joined: Fri Mar 28, 2003 8:51 pm
Contact:
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.
Partha Pratim Biswas

Cool Guyz
New poster
Posts: 2
Joined: Sat Jun 07, 2003 9:12 pm

### 191 WA!!

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]