10902 - Pick-up Sticks

[Darko]

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

[w k]

I'm getting WA.
What is correct output for:
4
0 0 0 1
0 1 1 1
1 1 1 0
1 0 0 0

my output is:

Top sticks: 4.

Is it correct? Any other I/O's?

[Darko]

That is correct. I'm too lazy to come up with test cases, but if you make some, post them and I'll run them.

[w k]

I'd do it but I've no idea what the critical inputs could be.
Wojciech

[Darko]

Neither do I, it looks straight forward as far as that part is concerned. What language are you using? If it's Pascal or Java, WA might be a RTE.

[w k]

I use C++. If there are no critical inputs it must be a simple mistake in the code. I'll look into. Thanks

Wojciech

[asif_rahman0]

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)

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

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

[rossi kamal]

Test case needed....

[Tahasin]

#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*/

[pointless0]

Just noting...for test cases:

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

uDebug AC output is:

Code: Select all

Top sticks: 1, 2.
Top sticks: 1, 2, 3, 4, 5, 6.

My AC output is:

Code: Select all

Top sticks: 2.
Top sticks: 5, 6.