866 - Intersecting Line Segments

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

Moderator: Board moderators

Post Reply
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

866 - Intersecting Line Segments

Post by Abednego »

Could anyone tell me what the output for these test case is?

Code: Select all

2

2
0 0 5 0
3 0 7 0

2
0 0 7 0
3 0 5 0
Or are these invalid test cases?

Thanks.
If only I had as much free time as I did in college...

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

Post by chuzpa »

I think they are invalid, because my acc program outputs

Code: Select all

2
For both of them.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 866

Post by CDiMa »

Abednego wrote:Or are these invalid test cases?

Thanks.
First I must say I didn't try to solve this problem.
'Problem setter' wrote:It is assumed, as a simplification, that no coincidences may occur between coordinates of singular points (intersections or end points).
I think this implies your test cases are invalid since the intersection of the segments has infinite coincidences...

Ciao!!!

Claudio

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Test case

Post by viniciusweb »

I'm getting presentation error (!). I'm printing "\n\n" after each number in the output (and already tried print just one "\n" and not printing after the last case).

Can someone post the correct output for the following test cases? Thanks.

Code: Select all

3

7
-1 -1 5 5
3 -2 3 9
4 -1 4 8
1 7 5 1
-1 6 9 8
7 3 9 4
9 1 11 3

2
1 1 7 7
2 2 9 9

4
1 1 7 7
1 0 5 5

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

My AC code gives..

Code: Select all

22\n
\n
4\n
\n
16\n

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Post by viniciusweb »

helloneo wrote:My AC code gives..

Code: Select all

22\n
\n
4\n
\n
16\n
hmm, my code outputs 23 and i drew the segments on paper and counted 23 too...

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

Oops.. Maybe my wrong program got accepted.. -_-;

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 866 - Intersecting Line Segments

Post by DD »

viniciusweb wrote:
helloneo wrote:My AC code gives..

Code: Select all

22\n
\n
4\n
\n
16\n


hmm, my code outputs 23 and i drew the segments on paper and counted 23 too...
My A.C. code outputs:

Code: Select all

23

2

16
It seems that test cases are generous. :oops:
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

huicpc0215
New poster
Posts: 2
Joined: Wed Oct 12, 2011 3:04 pm

866- WHY get WA?

Post by huicpc0215 »

who can give me some test case?
thanks. :roll: :roll:
Last edited by huicpc0215 on Thu Oct 13, 2011 7:48 pm, edited 1 time in total.

huicpc0215
New poster
Posts: 2
Joined: Wed Oct 12, 2011 3:04 pm

Re: 866- WHY get WA?

Post by huicpc0215 »

this is my code.
this is my solution:
every segment, intersect with every other segment,count how many parts can be divided. at lase, get the sum.
who can help me?



#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string.h>
using namespace std;

#define sgn(a) (a)>eps?1:((a)<-eps?-1:0)
#define MAXN 110
#define eps 1e-5
#define INF 1e9
struct pt {
double x,y;
pt(){x=0;y=0;}
pt(double a,double b){x=a;y=b;}
pt operator -(const pt &a)const {return pt(x-a.x,y-a.y);}
pt operator +(const pt &a)const {return pt(x+a.x,y+a.y);}
double operator *(const pt &a)const {return x*a.x+y*a.y;}
double operator ^(const pt &a)const {return x*a.y-y*a.x;}
pt operator *(const double &a)const {return pt(x*a,y*a);}
}pnt[10000];
bool eql(pt a,pt b)
{
if(fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps)return true;
return false;
}
struct line{
pt a,b;
}li[10000];
int dblcmp(double d)
{
if(fabs(d)<eps)return 0;
return (d>0)?1:-1;
}
int SegCross(pt p1,pt p2,pt p3,pt p4,pt &p) //if intersect,get intersectPoint
{
double s1,s2,s3,s4;
int d1,d2,d3,d4;
d1=dblcmp(s1=p2-p1^p3-p1); //s1=fabs(area(p1,p2,p3)*2);
d2=dblcmp(s2=p2-p1^p4-p1); //s2=fabs(area(p1,p2,p4)*2);
d3=dblcmp(s3=p4-p3^p1-p3); //s3=fabs(area(p3,p4,p1)*2);
d4=dblcmp(s4=p4-p3^p2-p3); //s4=fabs(area(p3,p4,p2)*2);
//printf("%d %d %d %d\n",d1,d2,d3,d4);
if((d1^d2)==-2&&(d3^d4)==-2) //if intersect , getPoint P
{
p.x=(p4.x*s1-p3.x*s2)/(s1-s2);
p.y=(p4.y*s1-p3.y*s2)/(s1-s2);
return 1;
}
if(d3==0&&(dblcmp((p3-p1)*(p4-p1))<=0)|| // p1 is on the line of p3 and p4
d4==0&&(dblcmp((p3-p2)*(p4-p2))<=0))return 0; // p2 is on the line of p3 and p4
if(d1==0&&(dblcmp((p1-p3)*(p2-p3))<=0)){p=p3;return 1;} // p3 is on the line of p1 and p2
if(d2==0&&(dblcmp((p1-p4)*(p2-p4))<=0)){p=p4;return 1;} // p4 is on the line of p1 and p2
return 0;
}
int main()
{
int t,cnt,n;
int k;
int ptcnt;
int ans;
pt tmp;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans=0;
for(int i=0;i<n;i++)
scanf("%lf%lf%lf%lf",&li.a.x,&li.a.y,&li.b.x,&li.b.y);
for(int i=0;i<n;i++)
{
ptcnt=0;cnt=1;
for(int j=0;j<n;j++)
{
if(j==i)continue;
if(SegCross(li.a,li.b,li[j].a,li[j].b,tmp))
{
for(k=0;k<ptcnt;k++)
if(eql(pnt[k],tmp))
break;
if(k==ptcnt)
{
pnt[ptcnt++]=tmp;
cnt++;
}
}
}
ans+=cnt;
}
printf("%d\n",ans);
if(t>1)printf("\n");
}
return 0;
}

Post Reply

Return to “Volume 8 (800-899)”