Page **2** of **2**

Posted: **Thu Jan 05, 2006 4:16 am**

by **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

Posted: **Fri Jul 07, 2006 10:13 pm**

by **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?

Posted: **Fri Jul 07, 2006 10:50 pm**

by **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.

Posted: **Fri Jul 07, 2006 11:17 pm**

by **w k**

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

Wojciech

Posted: **Sat Jul 08, 2006 12:32 am**

by **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.

Posted: **Sat Jul 08, 2006 1:28 pm**

by **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

Posted: **Sat Jul 08, 2006 2:30 pm**

by **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

Posted: **Sun Nov 25, 2007 9:14 pm**

by **rossi kamal**

Test case needed....

### why wa

Posted: **Thu Sep 03, 2009 11:49 am**

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

### Re: 10902 - Pick-up Sticks

Posted: **Tue Mar 29, 2016 1:34 am**

by **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: