| ||||||||||
| 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 | |||||||||
TLE 各位大侠,请问这个怎么优化?/*pku 2653 Pick-up sticks 051221 */
#include<stdio.h>
#define N 100000
typedef struct line{
float x1,x2,y1,y2;
long flag;
}LINE;
int intersect(LINE* l1,LINE* l2)
{
float dx,dy;
dx=l1->x1-l1->x2,dy=l1->y1-l1->y2;
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 x1,y1,x2,y2;
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",&x1,&y1,&x2,&y2);
(top[jj].x1)=x1,(top[jj].y1)=y1,(top[jj].x2)=x2,(top[jj].y2)=y2;
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