poj2653（判斷兩線段相交）

題目鏈接：poj2653

大意：有很多根木棍，如果後面的木根和前面的木棍有交叉的話，後面的木棍就會覆蓋掉前面的木棍，問最後沒有被覆蓋的木棍數

思路：運用隊列模擬，如果當前輸入的木棍和前面的木棍交叉，那麼將前面的那個木棍取出隊列，否則的話，將從隊列中取出的木棍再次入隊

#include 
#include 
#include 
#include 
using namespace std;
typedef pair pdd;
double direction(pdd p1, pdd p2, pdd p3)//求向量的叉積
{
    pdd d1 = make_pair(p3.first - p1.first, p3.second - p1.second);
    pdd d2 = make_pair(p2.first - p1.first, p2.second - p1.second);
    return d1.first*d2.second - d1.second*d2.first;
}
bool on_segment(pdd p1, pdd p2, pdd p3)//判斷一條線段的端點是否在另一條線段上
{
    double min_x = p1.first < p2.first ? p1.first : p2.first;
    double max_x = p1.first > p2.first ? p1.first : p2.first;
    if(min_x <= p3.first && p3.first <= max_x)//判斷p3的x坐標是否在p1和p2之間
        return true;
    else
        return false;
}
bool SegmentIntersect(pdd p1, pdd p2, pdd p3, pdd p4)
{
    double d1 = direction(p1, p2, p3);
    double d2 = direction(p1, p2, p4);
    double d3 = direction(p3, p4, p1);
    double d4 = direction(p3, p4, p2);
    if(d1*d2 < 0 && d3*d4 < 0)
        return true;
    else if(d1 == 0 && on_segment(p1, p2, p3))
        return true;
    else if(d2 == 0 && on_segment(p1, p2, p4))
        return true;
    else if(d3 == 0 && on_segment(p3, p4, p1))
        return true;
    else if(d4 == 0 && on_segment(p3, p4, p2))
        return true;
    else
        return false;
}
struct point
{
    double x1,y1,x2,y2;
    int id;
}s;
void solve(int n)
{
    queue  q;
    scanf("%lf%lf%lf%lf",&s.x1,&s.y1,&s.x2,&s.y2);
    s.id = 1;
    q.push(s);
    for(int i = 2; i <= n; i ++)
    {
        scanf("%lf%lf%lf%lf",&s.x1,&s.y1,&s.x2,&s.y2);
        s.id = i;
        q.push(s);
        while(!q.empty())
        {
            point tmp = q.front();
            q.pop();
            if(s.id == tmp.id)//隊列中的所有元素都判斷過了
            {
                q.push(s);
                break;
            }
            pdd p1 = make_pair(s.x1, s.y1);
            pdd p2 = make_pair(s.x2, s.y2);
            pdd p3 = make_pair(tmp.x1, tmp.y1);
            pdd p4 = make_pair(tmp.x2, tmp.y2);
            if(!SegmentIntersect(p1,p2,p3,p4))//不交叉
            {
                q.push(tmp);
            }
        }
    }
    s = q.front(); q.pop();
    printf("Top sticks: %d",s.id);
    while(!q.empty())
    {
        s = q.front();
        q.pop();
        printf(", %d",s.id);
    }
    printf(".\n");
}
int main()
{
    int n,i,j;
    while(scanf("%d",&n),n)
    {
        solve(n);
    }
    return 0;
}