poj 2653 Pick-up sticks

這是一個計算幾何的題目。題意是，按順序給一系列的線段，問最終哪些線段處在頂端。
   只需要窮舉判斷，當前的線段會與哪些線段有交點即可。也就是暴力求解，但是線段數目N有10的5次方，平方算法是不能過的。這個題
能過的原因是題目描述裡面說了，top的stick不會超過1000個。那麼修改下暴力的方式題目就能過了。
   從小到大枚舉每個棍子，判斷它是否與後面的棍子相交，如果相交直接把當前棍子的top屬性置為false，然後break內層循環。這樣就不
會超時了，暴力也是需要技巧的，這句話說的很對啊。
   判斷2條線段是否相交的算法直接按照黑書上的模板代碼寫了，那個模板代碼還不錯吧。。。

   代碼如下：
  
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N (100000 + 10)
struct POS
{
    double fX;
    double fY;
};

POS begs[MAX_N], ends[MAX_N];
bool bAns[MAX_N];
int nN;
const double fPrecision = 1e-8;

double Det(double fX1, double fY1, double fX2, double fY2)
{
    return fX1 * fY2 - fX2 * fY1;
}

//以a作為公共點,計算叉積
double Cross(POS& a, POS& b, POS& c)
{
    return Det(b.fX - a.fX, b.fY - a.fY, c.fX - a.fX, c.fY - a.fY);
}

int DblCmp(double fD)
{
    if (fabs(fD) < fPrecision)
    {
        return 0;
    }
    else
    {
        return fD > 0 ? 1 : -1;
    }
}
//
bool IsSegCross(int nI, int nJ)
{
    return (DblCmp(Cross(begs[nI], ends[nI], begs[nJ]))
            ^ DblCmp(Cross(begs[nI], ends[nI], ends[nJ]))) == -2
        && (DblCmp(Cross(begs[nJ], ends[nJ], begs[nI]))
            ^ DblCmp(Cross(begs[nJ], ends[nJ], ends[nI]))) == -2;
}

int main()
{
    while (scanf("%d", &nN), nN)
    {
        for (int i = 1; i <= nN; ++i)
        {
            scanf("%lf%lf%lf%lf", &begs[i].fX, &begs[i].fY,
                  &ends[i].fX, &ends[i].fY);
        }
       
        memset(bAns, true, sizeof(bAns));
       
        //暴力也是需要技巧的
        for (int i = 1; i < nN; ++i)
        {
            for (int j = i + 1; j <= nN; ++j)
            {
                if (IsSegCross(i, j))
                {
                    bAns[i] = false;
                    break;
                }
            }
        }
       
        printf("Top sticks:");
        bool bPre = false;
        for (int i = 1; i <= nN; ++i)
        {
            if (bAns[i])
            {
                if (bPre)
                {
                    printf(",");
                }
                bPre = true;
                printf(" %d", i);
            }
        }
        printf(".\n");
    }
   
    return 0;
}