866 - Intersecting Line Segments

[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.

[chuzpa]

I think they are invalid, because my acc program outputs

Code: Select all

2

For both of them.

[CDiMa]

Or are these invalid test cases?

Thanks.

First I must say I didn't try to solve this problem.

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]

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]

My AC code gives..

Code: Select all

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

[viniciusweb]

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]

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

[DD]

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.

[huicpc0215]

who can give me some test case?
thanks.

[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;
}