10902 - Pick-up Sticks

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Jan 05, 2006 4:16 am

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
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Fri Jul 07, 2006 10:13 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Jul 07, 2006 10:50 pm

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
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Fri Jul 07, 2006 11:17 pm

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sat Jul 08, 2006 12:32 am

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
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Sat Jul 08, 2006 1:28 pm

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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sat Jul 08, 2006 2:30 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)

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
New poster
Posts: 14
Joined: Mon Sep 03, 2007 10:11 am
Contact:

Post by rossi kamal » Sun Nov 25, 2007 9:14 pm

Test case needed....

Tahasin
New poster
Posts: 6
Joined: Tue Jun 27, 2006 7:19 am

why wa

Post by Tahasin » Thu Sep 03, 2009 11:49 am

#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
New poster
Posts: 9
Joined: Wed Jan 13, 2016 3:24 am

Re: 10902 - Pick-up Sticks

Post by pointless0 » Tue Mar 29, 2016 1:34 am

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.

Post Reply

Return to “Volume 109 (10900-10999)”