191 - Intersection

[FlyDeath]

I don't know what's wrong with my code....

#include <stdio.h>

class point
{
public:
double x,y;
};

class line
{
public:
point p1,p2;
};

int ccw(point p1, point p2, point p3)
{
double dx1, dx2, dy1, dy2;
dx1 = p2.x - p1.x; dy1 = p2.y - p1.y;
dx2 = p3.x - p2.x; dy2 = p3.y - p2.y;
if (dy1/dx1 <= dy2/dx2) return 1;
else return 0;
}

int intersect(line l1, line l2)
{
return ((ccw(l1.p1, l1.p2, l2.p1) != ccw(l1.p1, l1.p2, l2.p2))&& (ccw(l2.p1, l2.p2, l1.p1) != ccw(l2.p1, l2.p2, l1.p2)));
}

void main()
{
int i=0,j=0;
int num=0;
double m=0;
double b=0;
double temp;
line lb,ll,lr,lt,cl;
double xs=0,ys=0,xe=0,ye=0,sxl=0,sxr=0,syt=0,syb=0;
scanf("%d",&num);
for(i=0;i<num;i++)
{
scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&xs,&ys,&xe,&ye,&sxl,&syt,&sxr,&syb);
lt.p1.x=sxl;
lt.p1.y=syt;
lt.p2.x=sxr;
lt.p2.y=syt;
lb.p1.x=sxl;
lb.p1.y=syb;
lb.p2.x=sxr;
lb.p2.y=syb;
ll.p1.x=sxl;
ll.p1.y=syt;
ll.p2.x=sxl;
ll.p2.y=syb;
lr.p1.x=sxr;
lr.p1.y=syt;
lr.p2.x=sxr;
lr.p2.y=syb;
cl.p1.x=xs;
cl.p1.y=ys;
cl.p2.x=xe;
cl.p2.y=ye;
if(intersect(lt,cl)||intersect(lb,cl)||intersect(lr,cl)||intersect(ll,cl))
printf("Tn");
else
printf("Fn");
}
}

[ftomi]

Here is the input what your program don't handle properly:

1
1 1 2 2 0 0 3 3

By the way, I've made the same mistake.

[FlyDeath]

my program get "F" for your input,is that right??
but i can figure out what your test case means... left top(0,0) and right buttom(3,3)??

[FlyDeath]

er.....sorry , my program get a "T", is that right??

[FlyDeath]

well....i've given up the method above...
I change my method to this:

#include <stdio.h>

long au,d,bu;

int check(long x,long y)
{
long ans;
ans=y*d-au-bu;
if(ans<0)
return 0;
else if(ans==0)
return 2;
else
return 1;
}

void main()
{
int i=0,j=0;
int num=0;
long xs=0,ys=0,xe=0,ye=0,sxl=0,sxr=0,syt=0,syb=0;
long temp;
int dot1,dot2;
int s1,s2,s3,s4;
scanf("%d",&num);
for(i=0;i<num;i++)
{
scanf("%ld %ld %ld %ld %ld %ld %ld %ld",&xs,&ys,&xe,&ye,&sxl,&syt,&sxr,&syb);
if(sxr<sxl)
{
temp=sxr;
sxr=sxl;
sxl=sxr;
}
if(syt<syb)
{
temp=syb;
syb=syt;
syt=temp;
}
if((xs<sxl&&xe<sxl)||(xs>sxr&&xe>sxr)||(ys>syt&&ye>syt)||(ys<syb&&ye<syb))
printf("Fn");
else
{
if(((xs==sxl||xs==sxr)&&(ys<=syt&&ys>=syb))||((ys==syt||ys==syb)&&(xs<=sxr&&xs>=sxl))||((xe==sxl||xe==sxr)&&(ye<=syt&&ye>=syb))||((ye==syt||ye==syb)&&(xe<=sxr&&xe>=sxl)))
printf("Tn");
else
{
if(xs<sxr&&xs>sxl&&ys<syt&&ys>syb)
dot1=1;
else
dot1=0;
if(xe<sxr&&xe>sxl&&ye<syt&&ye>syb)
dot2=1;
else
dot2=0;
if(dot2==1&&dot1==1)
printf("Fn");
else if(dot2!=dot1)
printf("Tn");
else if(dot1==0&&dot2==0)
{
d=xs-xe;
au=ys-ye;
bu=ye*xs-ys*xe;
s1=check(sxr,syt);
s2=check(sxl,syt);
s3=check(sxr,syb);
s4=check(sxl,syb);
if((s1+s2+s3+s4)%4==0)
{
if(s1==2||s2==2||s3==2||s4==2)
printf("Tn");
else
printf("Fn");
}
else
printf("Tn");
}
}
}
}
}
can someone find my mistake??Thanks a lot

[ftomi]

"The terms top left and bottom right do not imply any ordering of coordinates."
But this is not why I've written the input file above:
"The rectangle consists of four straight lines and the area in between"
Your second progam is also get 'F' intead of 'T' for it.

[FlyDeath]

yes....I've fixed it...and still got WA..
It quite strange...

[ftomi]

Your program can't handle this input: (if you haven't fixed it yet)
1
2 5 2 0 1 1 4 4

[FlyDeath]

ya...I've fixed it , and still WA...

[FlyDeath]

I fixed my check function into this:

int check(double x,double y)
{
double ans;
if(d==0)
{
if(x>xs)
return 1;
else if(x==xs)
return 2;
else
return 0;
}
else
{
ans=y*d-au-bu;
if(ans<0)
return 0;
else if(ans==0)
return 2;
else
return 1;
}
}

I think it works fine , there must be some other problem i havent notice...I'm trying to find that...

[FlyDeath]

I've found another mistake.... but still WA..
here is whole of my code:

#include <stdio.h>

long au,d,bu;
long xs=0,ys=0,xe=0,ye=0,sxl=0,sxr=0,syt=0,syb=0;

int check(long x,long y)
{
long ans;
if(d==0)
{
if(x>xs)
return 1;
else if(x==xs)
return 2;
else if(x<xs)
return 0;
}
else
{
ans=y*d-au*x-bu;
if(ans<0)
return 0;
else if(ans==0)
return 2;
else if(ans>0)
return 1;
}
}

void main()
{
int i=0,j=0;
int num=0;
long temp;
int dot1,dot2;
int s1,s2,s3,s4;
scanf("%d",&num);
for(i=0;i<num;i++)
{
scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&xs,&ys,&xe,&ye,&sxl,&syt,&sxr,&syb);
if(sxr<sxl)
{
temp=sxr;
sxr=sxl;
sxl=sxr;
}
if(syt<syb)
{
temp=syb;
syb=syt;
syt=temp;
}
if((xs<sxl&&xe<sxl)||(xs>sxr&&xe>sxr)||(ys>syt&&ye>syt)||(ys<syb&&ye<syb))
printf("Fn");
else
{
if(xs<=sxr&&xs>=sxl&&ys<=syt&&ys>=syb)
dot1=1;
else
dot1=0;
if(xe<=sxr&&xe>=sxl&&ye<=syt&&ye>=syb)
dot2=1;
else
dot2=0;
if(dot1==0&&dot2==0)
{
d=xs-xe;
au=ys-ye;
bu=ye*xs-ys*xe;
s1=check(sxr,syt);
s2=check(sxl,syt);
s3=check(sxr,syb);
s4=check(sxl,syb);
if((s1==0&&s2==0&&s3==0&&s4==0)||(s1==1&&s2==1&&s3==1&&s4==1))
printf("Fn");
else
printf("Tn");
}
else
printf("Tn");
}
}
}

[FlyDeath]

I've got it right....Thanks a lot

[Alexandru Mosoi]

This is my source...

#include <stdio.h>

#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))

// intersection with a verical line

int vli(long long xs, long long ys, long long xe, long long ye, long long x, long long y1, long long y2)
{
if(min(xs, xe) > x || max(xs, xe) < x) return 0;

long long a = ys - (long long)ye;
long long b = xe - xs;
long long c = ye * xs - ys * xe;

if(b < 0) a = -a, b = -b, c = -c;
long long y = - c - a * x;

return y1 * b <= y && y <= y2 * b;
}

// intersection with a horizontal line

int hli(long long xs, long long ys, long long xe, long long ye, long long y, long long x1, long long x2)
{
if(min(ys, ye) > y || max(ys, ye) < y) return 0;

long long a = ys - ye;
long long b = xe - xs;
long long c = ye * xs - ys * xe;

if(a < 0) a = -a, b = -b, c = -c;
long long x = - c - b * y;

return x1 * a <= x && x <= x2 * a;
}

int main(void)
{
int n;
long xs, ys, xe, ye;
long x1, x2, y1, y2;

scanf("%d", &n);

for(; n > 0; n --)
{
scanf("%ld%ld%ld%ld", &xs, &ys, &xe, &ye);
scanf("%ld%ld%ld%ld", &x1, &y1, &x2, &y2);

if(x2 < x1)
{
int tmp = x1;
x1 = x2;
x2 = tmp;
} // now x2 >= x1

if(y2 < y1)
{
int tmp = y1;
y1 = y2;
y2 = tmp;
} // now y2 >= y1

int f =
(x1 <= xs && xs <= x2 && y1 <= ys && ys <= y2) ||
(x1 <= xe && xe <= x2 && y1 <= ye && ye <= y2) ||
hli(xs, ys, xe, ye, y1, x1, x2) ||
hli(xs, ys, xe, ye, y2, x1, x2) ||
vli(xs, ys, xe, ye, x1, y1, y2) ||
vli(xs, ys, xe, ye, x2, y1, y2);
if(f) printf("Tn");
else printf("Fn");
}
fflush(stdout);

return 0;
}

I don't know what's wrong with it. I always get WA.

[paulhryu]

I tried something like that, didn't work, did THIS and still doesn't work, but I swear it works with everything I've tried:

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID: 17243NT 191 C++ "Algebra" */

// Send to judge@uva.es

#include <iostream.h>
#include <fstream.h>

#ifdef ONLINE_JUDGE
#define ins cin
#define outs cout
#else
#define ins fin
#define outs fout
ifstream fin("myprog.in");
ofstream fout("myprog.out");
#endif

typedef struct {
int x;
int y;
} point;

typedef struct {
point p1;
point p2;
} line;

int ccw(point p0, point p1, point p2);
int intersect(line l1, line l2);

int main() {
int ncase;
int xmin, ymin;
int xmax, ymax;

line ln;
line rect1, rect2, rect3, rect4;

ins >> ncase;
while(ncase-- > 0) {
ins >> ln.p1.x >> ln.p1.y >> ln.p2.x >> ln.p2.y;
ins >> xmin >> ymax >> xmax >> ymin;

rect1.p1.x = xmin, rect1.p1.y = ymin;
rect1.p2.x = xmax, rect1.p2.y = ymin;
rect2.p1.x = xmin, rect2.p1.y = ymin;
rect2.p2.x = xmin, rect2.p2.y = ymax;
rect3.p1.x = xmin, rect3.p1.y = ymax;
rect3.p2.x = xmax, rect3.p2.y = ymax;
rect4.p1.x = xmax, rect4.p1.y = ymin;
rect4.p2.x = xmax, rect4.p2.y = ymax;

if(intersect(ln, rect1) || intersect(ln, rect2) ||
intersect(ln, rect3) || intersect(ln, rect4))
outs << "Tn";
else outs << "Fn";
}

return 0;
}

int ccw(point p0, point p1, point p2) {
int dx1, dx2, dy1, dy2;

dx1 = p1.x - p0.x; dy1 = p1.y - p0.y;
dx2 = p2.x - p0.x; dy2 = p2.y - p0.y;
if(dx1 * dy2 > dy1 * dx2) return 1;
if(dx1 * dy2 < dy1 * dx2) return -1;
if((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) return -1;
if((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) return 1;

return 0;
}

int intersect(line l1, line l2) {
int ccw11 = ccw(l1.p1, l1.p2, l2.p1);
int ccw12 = ccw(l1.p1, l1.p2, l2.p2);
int ccw21 = ccw(l2.p1, l2.p2, l1.p1);
int ccw22 = ccw(l2.p1, l2.p2, l1.p2);

return ((ccw11 * ccw12 < 0) && (ccw21 * ccw22 < 0)) || (ccw11 * ccw12 * ccw21 * ccw22 == 0);
}

// @END_OF_SOURCE_CODE

[tam]

I don't know why......
My Alogrithm and code are very easy......
Please help....... Thanks


[pascal]
program p191;
var
tin:Text;
i,n:integer;
sx,sy,ex,ey:real;
rx1,ry1,rx2,ry2:real;
m:real;
within:boolean;
forx,fory:real;
ch:char;

function findx(y:real):real;
begin
findx:= sx + (y - sy)/m;
end;

function findy(x:real):real;
begin
findy:= sy + m*(x - sx);
end;

begin

readln(n);
for i:=1 to n do
begin
within:=false;
readln(sx,sy,ex,ey,rx1,ry1,rx2,ry2);
if (sx = ex) then
begin
if (sx >= rx1) and (sx <= rx2) then
within:=true;
end
else
if (sy = ey) then
begin
if (sy >= ry2) and (sy <= ry1) then
within:=true;
end
else
begin
m:=(sy - ey) / (sx - ex);
forx:=findx(ry1);

if (forx >= rx1) and (forx <= rx2) then
within:=true;
forx:=findx(ry2);

if (forx >= rx1) and (forx <= rx2) then
within:=true;
fory:=findy(rx1);

if (fory >= ry2) and (fory <= ry1) then
within:=true;
fory:=findy(rx2);

if (fory >= ry2) and (fory <= ry1) then
within:=true;
end;



if (within) then
ch:='T'
else
ch:='F';

if (i = n) then
writeln(ch)
else
write(ch,' ');

end;


end.

[/pascal]