10902 - Pick-up 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 15-20x 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 15-20x 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
(x-x1)/(x2-x1)=(y-y1)/(y2-y1) = constant(c1)
so, x=x1+c1(x2-x1)
Similarly, for another line we got x=x3+c2(x4-x3)
we got x1+c1(x2-x1)=x3+c2(x4-x3)
similarly y1+c1(y2-y1)=y3+c2(y4-y3)
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
(x-x1)/(x2-x1)=(y-y1)/(y2-y1) = constant(c1)
so, x=x1+c1(x2-x1)
Similarly, for another line we got x=x3+c2(x4-x3)
we got x1+c1(x2-x1)=x3+c2(x4-x3)
similarly y1+c1(y2-y1)=y3+c2(y4-y3)
Code: Select all
c1=(x4-x3)(y1-y3)-(y4-y3)(x1-x3)/(y4-y3)(x2-x1)-(x4-x3)(y2-y1)
c2=(x2-x1)(y1-y3)-(y2-y1)(x1-x3)/(y4-y3)(x2-x1)-(x4-x3)(y2-y1)
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 = x1-x2;
b = y1-y2;
c = xm-xn;
d = ym-yn;
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 = x1-x2;
b = y1-y2;
c = xm-xn;
d = ym-yn;
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 - Pick-up 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.