191 - Intersection
Moderator: Board moderators
- 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 ?
I am confused !


Can anybody explain ?The terms top left and bottom right do not imply any ordering of coordinates.

-
- 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).
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]
[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
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]
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

01314075_24.c

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]
-
- 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 (/* ... */)
// 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 (/* ... */)
191 Wrong Answer
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.
Here are some testdata.
input:
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
output:
good luck~ 
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

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