hdu_1147 Pick_up sticks

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.

Input Input consists of a number of cases. The data for each case start with 1 ≤ n ≤ 100000, the number of sticks fZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciB0aGlzIGNhc2UuIFRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb250YWluIGZvdXIgbnVtYmVycyBlYWNoLCB0aGVzZSBudW1iZXJzIGFyZSB0aGUgcGxhbmFyIGNvb3JkaW5hdGVzIG9mIHRoZSBlbmRwb2ludHMKIG9mIG9uZSBzdGljay4gVGhlIHN0aWNrcyBhcmUgbGlzdGVkIGluIHRoZSBvcmRlciBpbiB3aGljaCBTdGFuIGhhcyB0aHJvd24gdGhlbS4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGVyZSBhcmUgbm8gbW9yZSB0aGFuIDEwMDAgdG9wIHN0aWNrcy4gVGhlIGlucHV0IGlzIGVuZGVkIGJ5IHRoZSBjYXNlIHdpdGggbj0wLiBUaGlzIGNhc2Ugc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuCjxicj4KCiAKPGJyPgpPdXRwdXQKRm9yIGVhY2ggaW5wdXQgY2FzZSwgcHJpbnQgb25lIGxpbmUgb2Ygb3V0cHV0IGxpc3RpbmcgdGhlIHRvcCBzdGlja3MgaW4gdGhlIGZvcm1hdCBnaXZlbiBpbiB0aGUgc2FtcGxlLiBUaGUgdG9wIHN0aWNrcyBzaG91bGQgYmUgbGlzdGVkIGluIG9yZGVyIGluIHdoaWNoIHRoZXkgd2VyZSB0aHJvd24uCjxicj4KVGhlIHBpY3R1cmUgdG8gdGhlIHJpZ2h0IGJlbG93IGlsbHVzdHJhdGVzIHRoZSBmaXJzdCBjYXNlIGZyb20gaW5wdXQuPGJyPgoKIAo8YnI+ClNhbXBsZSBJbnB1dAoKPHByZSBjbGFzcz0="brush:java;">5 1 1 4 2 2 3 3 1 1 -2.0 8 4 1 4 8 2 3 3 6 -2.0 3 0 0 1 1 1 0 2 1 2 0 3 1 0
Sample Output

Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.

分析：

解題思路比較簡單——每放一根棍子，都判斷一下它與它前面的且在頂端的棍子是否相交，相交的話則將相應的棍子從解空間中除去（當前這根暫時是在解空間中的）

但是，如果直接用數組做會超時，然後用鏈表做（剛開始自己寫了個鏈表，但是寫壞掉了，哎，基礎啊……），於是最後還是用了list

除數據結構外，最主要的算法就是判斷兩直線相交了，直接用了模板

代碼：

//hdu 1147
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const double eps=1e-8;

int sgn(double x)
{
    if(fabs(x)=min(l2.s.x,l2.e.x) &&
    max(l2.s.x,l2.e.x) >=min(l1.s.x,l1.e.x) &&
    max(l1.s.y,l1.e.y) >=min(l2.s.y,l2.e.y) &&
    max(l2.s.y,l2.e.y) >=min(l1.s.y,l1.e.y) &&
    sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0 &&
    sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=0 ;
}

int main()
{
    freopen("in.txt","r",stdin);
    int n;
    int len;
    node cur;
    list stick;
    list::iterator p;

    while(scanf("%d",&n),n){

        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&cur.t.s.x,&cur.t.s.y,&cur.t.e.x,&cur.t.e.y);
            cur.no=i;
            stick.push_back(cur);

            if(i>1){
                p=stick.begin();
                len=stick.size();
                for(int i=1;i