Page 5 of 7
Posted: Thu Jun 19, 2003 7:09 am
by paulhryu
Two things you never do with floats and doubles:
1. Compare them directly.
2. Converting them directly to integers.
You suffer from the first problem. NEVER compare floats directly. Due to rounding errors, you may have minute differences that make the internal representations different.
Instead of a == b, use fabs(a - b) < ERROR, for which ERROR = .00000001 or some other small, but not too small, number. If you don't want to use fabs, then here's a macro for you to use:
#define ERROR .00000001
#define float_equals(a,b) (a - b < ERROR && b - a < ERROR)
The same applies to greater than and less than.
#define float_isless(a, b) (b - a > ERROR)
Now, the other part of your code. I don't feel like going through it. It's probably the right algorithm. But on these computational geometry problems, you can never go wrong with premanufactured algorithms. They will save you time, and though these algebraic solutions are great, the problem is they often have little exceptions and such.
For a great source of those precanned geometry algorithms, go to
http://www.softsurfer.com which has excellent solutions for convex hulls, intersections, area, inclusion in polygon (very useful), you name it.
In this case, divide the rectangle into four lines and do intersections for each. Believe me, this works a lot better than solving equations with algebra and you'll get more accepted this way.
But do correct your program to account for rounding errors.
Posted: Thu Jun 19, 2003 8:36 pm
by Cool Guyz
thx, i already found the mistakes
but it will try ur way too
look like it can be more simple
than my solution
thx again
191 WA , plizzzzzzzzzzzz help me
Posted: Thu Aug 14, 2003 10:41 pm
by Riyad
[c]
i dont find any prob with my algorithm and cant find any problem with my code, pliiiiiiiiiiiiizzzzzzzzzz help. here is my code
Code: Select all
#include<stdio.h>
struct point {
long int x,y;
}a,b,c,d,e,f;
#define max(a,b) ((a)>(b)? (a): (b))
#define min(a,b) ((a)>(b)? (b):(a))
int direction(struct point pi,struct point pj,struct point pk){
return ((pk.x-pi.x)*(pj.y-pi.y)-(pj.x-pi.x)*(pk.y-pi.y));
}
int on_segment(struct point pi,struct point pj,struct point pk){
if((max(pi.x,pj.x)>=pk.x && pk.x>= min(pi.x,pj.x))&&(max(pi.y,pj.y)>=pk.y&& pk.y>=min(pi.y,pj.y)))
return 1;
else
return 0;
}
int intersect(struct point p1,struct point p2,struct point p3,struct point p4){
long int d1,d2,d3,d4;
d1=direction(p3,p4,p1);
d2=direction(p3,p4,p2);
d3=direction(p1,p2,p3);
d4=direction(p1,p2,p4);
if(((d1>0&& d2<0)|| (d1<0&&d2>0)) && ((d3>0&&d4<0)||(d3<0&&d4>0)))
return 1;
else if(d1==0 && on_segment(p3,p4,p1))
return 1;
else if(d2==0 && on_segment(p3,p4,p2))
return 1;
else if(d3==0 && on_segment(p1,p2,p3))
return 1;
else if(d4==0 && on_segment(p1,p2,p4))
return 1;
else
return 0;
}
int main(){
long int cases;
long int xl,xr,yt,yb;
long int xs,ys,xe,ye;
int flag1,flag2,flag3,flag4;
freopen("input.in","rt",stdin);
freopen("E:\out.txt","wt",stdout);
scanf("%ld",&cases);
while(cases>0){
scanf("%ld %ld %ld %ld %ld %ld %ld %ld",&xs,&ys,&xe,&ye,&xl,&yt,&xr,&yb);
a.x=xl;a.y=yt;
c.x=xr;c.y=yb;
b.x=xr;b.y=yt;
d.x=xl;d.y=yb;
e.x=xs;e.y=ys;
f.x=xe;f.y=ye;
flag1=intersect(a,b,e,f);
flag2=intersect(b,c,e,f);
flag3=intersect(c,d,e,f);
flag4=intersect(d,a,e,f);
if(flag1==0&& flag2==0 && flag3==0 && flag4==0){
printf("F\n");
}
else if(flag1==1||flag2==1||flag3==1||flag4==1){
printf("T\n");
}
cases--;
}
return 0;
}
thanx in advance
Riyad
[/c]
Posted: Sat Aug 16, 2003 12:34 am
by UFP2161
The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid.
Posted: Sun Aug 17, 2003 5:59 am
by Joseph Kurniawan
There's a sample I/O available in page 5 written ( the Author is haquin) in this Volume. Try with those, maybe they will help.
Posted: Sun Aug 17, 2003 6:11 am
by Joseph Kurniawan
Here's the sample 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
And the Output will be
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
Posted: Tue Mar 09, 2004 8:13 am
by Almost Human
I am having problem on this and am looking for your help.
I couldn't figure out why for this input :
2 4 4 2 1 1 11 11
the output is :
T
because, as far as I know, the line would be inside the rectangle ... or have I made mistake somewhere?
thank you
Posted: Tue Mar 09, 2004 11:25 am
by the LA-Z-BOy
to
Almost Human:
As UFP2161 already figured out from the problem statement, the definition of
intersection is
The line is said to intersect the rectangle if the line and the rectangle have at least one point in common.
In the sample you mentioned, all the points of
the line is common with
the rectangle. Hence it
intersects and therefore output should be T.
Hope i'm clear.
Posted: Tue Mar 09, 2004 2:22 pm
by alu_mathics
remember that in this problem
xtop<=xbottom
ytop>=ybottom
are not always true.
so you should consider this case.
Hope this will help you.
191 WA
Posted: Mon Sep 13, 2004 1:10 pm
by Gazi Shaheen Hossain
why this gives WA?
help me plz.
[cpp]#include <stdio.h>
void main()
{
long double xstart,ystart,xend,yend,xleft,ytop,xright,ybottom;
long double x,x1,x2,y,y1,y2,xmax,xmin,ymax,ymin;
while(scanf("%Lf %Lf %Lf %Lf %Lf %Lf %Lf %Lf",
&xstart,&ystart,&xend,¥d,&xleft,&ytop,&xright,&ybottom)==8)
{
x1=xstart;x2=xend;y1=ystart;y2=yend;
y=ytop;
x=(y-y1)*(x1-x2)/(y1-y2)+x1;
if(x>=xleft&&x<=xright)
{printf("T\n");continue;}
y=ybottom;
x=(y-y1)*(x1-x2)/(y1-y2)+x1;
if(x>=xleft&&x<=xright)
{printf("T\n");continue;}
x=xleft;
y=(x-x1)*(y1-y2)/(x1-x2)+y1;
if(y>=ybottom&&y<=ytop)
{printf("T\n");continue;}
x=xright;
y=(x-x1)*(y1-y2)/(x1-x2)+y1;
if(y>=ybottom&&y<=ytop)
{printf("T\n");continue;}
printf("F\n");
}
}[/cpp]
Slope
Posted: Tue Sep 28, 2004 8:45 pm
by Ndiyaa ndako
What happens if y1=y2?
Posted: Sat Jul 09, 2005 3:38 pm
by shamim
alu_mathics wrote:remember that in this problem
xtop<=xbottom
ytop>=ybottom
are not always true.
so you should consider this case.
Hope this will help you.
Yes, this is indeed true. I got plenty of wrong answers for this.
But what bothered me
is, whenever a problem statement says left and top, they better use what they say, and not introduce contradictory critical inputs.
Posted: Sun Aug 14, 2005 7:54 am
by shu
The terms top left and bottom right do not imply any ordering of coordinates.
It means 'left' in this problem is not really-left in common sense
tricky statement it is.
191 Wrong Answer
Posted: Tue Jul 25, 2006 2:05 pm
by Anupam Pathak
hi all,
i am trying to solve 191 Intersection in C++ but I am getting WA. I have considered as much cases as I could. My code is:-
#include<iostream>
using namespace std;
int check(float,float,float,float,float,float);
int main()
{
int N,i=0;
cin>>N;
float m,c,x,y;
int xstart,xend,ystart,yend,xleft,ytop,xright,ybottom,temp;
while(i!=N)
{
cin>>xstart>>ystart>>xend>>yend>>xleft>>ytop>>xright>>ybottom;
while(1)
{
if(((xstart<=xleft)&&(xstart>=xright))||((xstart>=xleft)&&(xstart<=xright)))
{
cout<<"T"<<endl;
break;
}
if(((xend<=xleft)&&(xend>=xright))||((xend>=xleft)&&(xend<=xright)))
{
cout<<"T"<<endl;
break;
}
if(xstart!=xend)
{
m=(float)(ystart-yend)/(float)(xstart-xend);
c=yend-(m*xend);
x=(ytop-c)/m;
if((x<=xright)&&(x>=xleft)&&check(xstart,ystart,xend,yend,x,ytop))
{
cout<<"T"<<endl;
break;
}
x=(ybottom-c)/m;
if((x<=xright)&&(x>=xleft)&&check(xstart,ystart,xend,yend,x,ybottom))
{
cout<<"T"<<endl;
break;
}
y=(m*xleft)+c;
if((y>=ybottom)&&(y<=ytop)&&check(xstart,ystart,xend,yend,xleft,y))
{
cout<<"T"<<endl;
break;
}
y=(m*xright)+c;
if((y>=ybottom)&&(y<=ytop)&&check(xstart,ystart,xend,yend,xright,y))
{
cout<<"T"<<endl;
break;
}
cout<<"F"<<endl;
break;
}
else
{
if((xstart>=xleft)&&(xstart<=xright)&&check(xstart,ystart,xend,yend,xstart,ytop))
{
cout<<"T"<<endl;
}
else
{
if((xstart>=xleft)&&(xstart<=xright)&&check(xstart,ystart,xend,yend,xstart,ybottom))
{
cout<<"T"<<endl;
}
else
cout<<"F"<<endl;
}
break;
}
}
i++;
}
return 0;
}
int check(float x1,float y1,float x2,float y2,float x,float y)
{
if(((x1<=x)&&(x2>=x))||((x1>=x)&&(x2<=x)))
{
if(((y1<=y)&&(y2>=y))||((y1>=y)&&(y2<=y)))
{
return 1;
}
}
return 0;
}
what's wrong with it........
Anupam Pathak
Posted: Thu Jul 27, 2006 6:17 pm
by 898989
Sorry i did not read your code
But her two notes...
In my code i remeember using epsilon for comparing floats
I remember there is a test case where line totaly inside rectangle
and this will be considered intersection
I hope this is useful