 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
brute force does not work for this problemIn Reply To:老是tle 怀疑是读入数据时的问题，我把intersect全部return 1 了还是tle ,帮忙看看 Posted by:ning at 2006-01-03 10:43:54
> if( (dx*(l2->y1-l1->y1)-dy*(l2->x1-l1->x1) )*
> (dx*(l2->y2-l1->y1)-dy*(l2->x2-l1->x1) )>0 )
> return 0;
> dx=l2->x1-l2->x2,dy=l2->y1-l2->y2;
>
> if( (dx*(l1->y1-l2->y1)-dy*(l1->x1-l2->x1) )*
> (dx*(l1->y2-l2->y1)-dy*(l1->x2-l2->x1) )>0 )
> return 0;
> return 1;
> }
> LINE top[N];
> int main()
> {
> float x11,y11,x21,y21;
> long sticks,ii,jj;
> for(;scanf("%ld",&sticks);)
> {
> if(!sticks)
> return;
> for(jj=0;jj<sticks;jj++)
> {
> top[jj].flag=jj+1;
> scanf("%f%f%f%f",&x11,&y11,&x21,&y21);
> (top[jj].x1)=(x11>x21)?x21:x11,
> (top[jj].y1)=(y11>y21)?y21:y11,
> (top[jj].x2)=(x11<x21)?x21:x11,
> (top[jj].y2)=(y11<y21)?y21:y11;
>
> for(ii=0;ii<jj;ii++)
> if(top[ii].flag&&intersect(&top[ii],&top[jj]))
> {
> top[ii].flag=0;
> }
> }
> printf("Top sticks: ");
> for(jj=0;!(top[jj].flag);jj++)
> ;
> printf("%ld",top[jj].flag);
> for(jj++;jj<sticks;jj++)
> if(top[jj].flag)
> printf(", %ld",top[jj].flag);
> printf(".\n");
> }
> }
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
