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