10902  Pickup Sticks
Moderator: Board moderators
Well, turns out that maintaining the flag array was too expensive or something.
I optimized all the wrong things (parsing, avoid floats..) so, in the end, when I got rid of the flag array and just loaded all segments and printed out all that are not intersecting with any that came later... I got it to 1.152. To be honest, I was rather impressed by the result (it's something like 1520x faster). This fast one checks a lot more segment pairs for intersection, go figure.
Keep in mind that it's Java. Just reading the segments took something like 5 secs originally.
Darko
I optimized all the wrong things (parsing, avoid floats..) so, in the end, when I got rid of the flag array and just loaded all segments and printed out all that are not intersecting with any that came later... I got it to 1.152. To be honest, I was rather impressed by the result (it's something like 1520x faster). This fast one checks a lot more segment pairs for intersection, go figure.
Keep in mind that it's Java. Just reading the segments took something like 5 secs originally.
Darko

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
I think no critical input for this one.
Its a classical problem on Computational Geometry.
Just A simple Geometry and some programming(algorithm) can solve
this problem easily within O(n^2).
From School,
We know the equation of line through two points(x1,y1) and (x2,y2) is
(xx1)/(x2x1)=(yy1)/(y2y1) = constant(c1)
so, x=x1+c1(x2x1)
Similarly, for another line we got x=x3+c2(x4x3)
we got x1+c1(x2x1)=x3+c2(x4x3)
similarly y1+c1(y2y1)=y3+c2(y4y3)
1)The denominators for the equations for c1 and c2 are the same.
2)If the denominator for the equations for c1 and c2 is 0 then the two lines are parallel.
3)If the denominator and numerator for the equations for c1 and c2 are 0 then the two lines are coincident.
Important:
The equations apply to lines, if the intersection of line segments is required then it is only necessary to test if c1 and c2 lie between 0 and 1. Whichever one lies within that range then the corresponding line segment contains the intersection point. If both lie within the range of 0 to 1 then the intersection point is within both line segments.

rabbi
Its a classical problem on Computational Geometry.
Just A simple Geometry and some programming(algorithm) can solve
this problem easily within O(n^2).
From School,
We know the equation of line through two points(x1,y1) and (x2,y2) is
(xx1)/(x2x1)=(yy1)/(y2y1) = constant(c1)
so, x=x1+c1(x2x1)
Similarly, for another line we got x=x3+c2(x4x3)
we got x1+c1(x2x1)=x3+c2(x4x3)
similarly y1+c1(y2y1)=y3+c2(y4y3)
Code: Select all
c1=(x4x3)(y1y3)(y4y3)(x1x3)/(y4y3)(x2x1)(x4x3)(y2y1)
c2=(x2x1)(y1y3)(y2y1)(x1x3)/(y4y3)(x2x1)(x4x3)(y2y1)
x = x1 + c1 (x2  x1)
y = y1 + c2 (y2  y1)
where x1,x2,y1,y2 is a line and x3,y3,x4,y4 is others line
2)If the denominator for the equations for c1 and c2 is 0 then the two lines are parallel.
3)If the denominator and numerator for the equations for c1 and c2 are 0 then the two lines are coincident.
Important:
The equations apply to lines, if the intersection of line segments is required then it is only necessary to test if c1 and c2 lie between 0 and 1. Whichever one lies within that range then the corresponding line segment contains the intersection point. If both lie within the range of 0 to 1 then the intersection point is within both line segments.

rabbi

 New poster
 Posts: 14
 Joined: Mon Sep 03, 2007 10:11 am
 Contact:
why wa
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
bool crosspoint(double x1,double y1,double x2,double y2,double xm,double ym,double xn,double yn);
double max(double a, double b)
{
return a>b ? a : b;
}
double min(double a, double b)
{
return a<b ? a : b;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
if(n == 0)break;
int count = 0;
double a[1005][5];
int stick[1005];
double x1,y1,x2,y2;
bool trac[1005];
for(int i = 1; i<=n; i++)
{
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
if(i == 1)
{
a[++count][1] = x1;
a[count][2] = y1;
a[count][3] = x2;
a[count][4] = y2;
stick[count] = i;
trac[count] = true;
continue;
}
bool tc = true;
for(int j = 1; j<=count; j++)
{
if(trac[j])
{
bool ch = crosspoint(a[j][1],a[j][2],a[j][3],a[j][4],x1,y1,x2,y2);
if(ch)
{
trac[j] = false;
}
}
if(tc && !trac[j])
{
tc = false;
trac[j] = true;
stick[j] = i;
a[j][1] = x1;
a[j][2] = y1;
a[j][3] = x2;
a[j][4] = y2;
}
}
if(tc)
{
a[++count][1] = x1;
a[count][2] = y1;
a[count][3] = x2;
a[count][4] = y2;
stick[count] = i;
trac[count] = true;
}
}
//sort(stick,stick+count);
int res[1006],in = 0;
printf("Top sticks: ");
for(int i = 1; i<=count; i++)if(trac)res[++in] = stick;//printf("%d ",stick);
sort(res,res+in);
for(int i = 1; i<in; i++)printf("%d, ",res);
printf("%d.\n",res[in]);
//cout<<endl;
}
return 0;
}
bool crosspoint(double x1,double y1,double x2,double y2,double xm,double ym,double xn,double yn)
{
double a,b,c,d;
double m,n;
double x,y;
a = x1x2;
b = y1y2;
c = xmxn;
d = ymyn;
m = (a*y1)  (b*x1);
n = (c*ym)  (d*xm);
double p,q,r,s;
p = (c*m)  (a*n);
q = (d*m)  (b*n);
r = (a*d)  (b*c);
if(r == 0) return false;
x = p/r;
y = q/r;
p = max(x1,x2);
q = min(x1,x2);
r = max(y1,y2);
s = min(y1,y2);
double e,f,g,h;
e = max(xm,xn);
f = min(xm,xn);
g = max(ym,yn);
h = min(ym,yn);
if(x>=q && x <=p && y>=s && y<=r && x>=f && x <=e && y>=h && y<=g) return true;
else return false;
}
/*any one can give me some critical test cases plzzzz*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
bool crosspoint(double x1,double y1,double x2,double y2,double xm,double ym,double xn,double yn);
double max(double a, double b)
{
return a>b ? a : b;
}
double min(double a, double b)
{
return a<b ? a : b;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
if(n == 0)break;
int count = 0;
double a[1005][5];
int stick[1005];
double x1,y1,x2,y2;
bool trac[1005];
for(int i = 1; i<=n; i++)
{
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
if(i == 1)
{
a[++count][1] = x1;
a[count][2] = y1;
a[count][3] = x2;
a[count][4] = y2;
stick[count] = i;
trac[count] = true;
continue;
}
bool tc = true;
for(int j = 1; j<=count; j++)
{
if(trac[j])
{
bool ch = crosspoint(a[j][1],a[j][2],a[j][3],a[j][4],x1,y1,x2,y2);
if(ch)
{
trac[j] = false;
}
}
if(tc && !trac[j])
{
tc = false;
trac[j] = true;
stick[j] = i;
a[j][1] = x1;
a[j][2] = y1;
a[j][3] = x2;
a[j][4] = y2;
}
}
if(tc)
{
a[++count][1] = x1;
a[count][2] = y1;
a[count][3] = x2;
a[count][4] = y2;
stick[count] = i;
trac[count] = true;
}
}
//sort(stick,stick+count);
int res[1006],in = 0;
printf("Top sticks: ");
for(int i = 1; i<=count; i++)if(trac)res[++in] = stick;//printf("%d ",stick);
sort(res,res+in);
for(int i = 1; i<in; i++)printf("%d, ",res);
printf("%d.\n",res[in]);
//cout<<endl;
}
return 0;
}
bool crosspoint(double x1,double y1,double x2,double y2,double xm,double ym,double xn,double yn)
{
double a,b,c,d;
double m,n;
double x,y;
a = x1x2;
b = y1y2;
c = xmxn;
d = ymyn;
m = (a*y1)  (b*x1);
n = (c*ym)  (d*xm);
double p,q,r,s;
p = (c*m)  (a*n);
q = (d*m)  (b*n);
r = (a*d)  (b*c);
if(r == 0) return false;
x = p/r;
y = q/r;
p = max(x1,x2);
q = min(x1,x2);
r = max(y1,y2);
s = min(y1,y2);
double e,f,g,h;
e = max(xm,xn);
f = min(xm,xn);
g = max(ym,yn);
h = min(ym,yn);
if(x>=q && x <=p && y>=s && y<=r && x>=f && x <=e && y>=h && y<=g) return true;
else return false;
}
/*any one can give me some critical test cases plzzzz*/

 New poster
 Posts: 9
 Joined: Wed Jan 13, 2016 3:24 am
Re: 10902  Pickup Sticks
Just noting...for test cases:
uDebug AC output is:
My AC output is:
Code: Select all
2
1 1 2 2
2 2 3 3
6
0 0 1 1
2 2 3 3
0 0 1 1
2 2 3 3
0 0 1 1
2 2 3 3
0
Code: Select all
Top sticks: 1, 2.
Top sticks: 1, 2, 3, 4, 5, 6.
Code: Select all
Top sticks: 2.
Top sticks: 5, 6.