/*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;
    if( (l1->x1>l2->x2) || (l1->y1>l2->y2) ||
        (l2->x1>l1->x2) || (l2->y1>l1->y2) )
        return 0;

    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 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");
    }
}

• brute force does not work for this problem (1322) achilles 2006-01-03 12:46:41
  • 难道还有O(N)的算法？？我没判断就输出都还要700多MS， (4) ning 2006-01-06 08:46:07
    • Re:难道还有O(N)的算法？？我没判断就输出都还要700多MS， (19) Bark 2007-12-05 16:33:13
      • Re:难道还有O(N)的算法？？我没判断就输出都还要700多MS， (23) njjinni 2009-05-30 11:44:43
  • Re:brute force does not work for this problem (49) Bark 2008-05-04 22:14:56