POJ 2653 線段與線段相交 Pick-up sticks

分析：每輸入一條線段，就將以前沒有踢除的線段與之有交點的都踢除．最後留下的就是在最上面的．

[cpp] 
#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
#include<iomanip>  
#include<vector>  
 
using namespace std; 
const int maxn=100000+100; 
 
struct point{ 
    double x,y; 
    void read(){ 
        scanf("%lf %lf",&x,&y); 
    } 
}; 
struct line{ 
    point st, en; 
    int k; 
    void read(int i){ 
        k=i; st.read(); en.read(); 
    } 
}Rt; 
double cross(point p0,point p1,point p2){ 
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 
} 
int work(line a,line b){ 
    double x = cross( a.st,a.en,b.st ); 
    double y = cross( a.st,a.en,b.en ); 
    if(x*y<=0)return 1; 
    return 0; 
} 
bool del(line x){ 
    if( work(x,Rt)&&work(Rt,x) )return true; 
    return false; 
} 
int main(){ 
    int n; 
    while(cin>>n,n){ 
        vector<line>M; 
        vector<line>::iterator it; 
        for(int i=1;i<=n;++i){ 
            Rt.read(i); 
            M.erase( remove_if(M.begin(),M.end(),del),M.end() ); 
            M.push_back(Rt); 
        } 
        printf("Top sticks:"); 
        for(it=M.begin();it!=M.end();++it){ 
            if(it+1==M.end()) 
                cout<<' '<<it->k<<'.'<<endl; 
            else cout<<' '<<it->k<<','; 
        } 
    } 
    return 0; 
} 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<vector>

using namespace std;
const int maxn=100000+100;

struct point{
    double x,y;
    void read(){
        scanf("%lf %lf",&x,&y);
    }
};
struct line{
    point st, en;
    int k;
    void read(int i){
        k=i; st.read(); en.read();
    }
}Rt;
double cross(point p0,point p1,point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int work(line a,line b){
    double x = cross( a.st,a.en,b.st );
    double y = cross( a.st,a.en,b.en );
    if(x*y<=0)return 1;
    return 0;
}
bool del(line x){
    if( work(x,Rt)&&work(Rt,x) )return true;
    return false;
}
int main(){
    int n;
    while(cin>>n,n){
        vector<line>M;
        vector<line>::iterator it;
        for(int i=1;i<=n;++i){
            Rt.read(i);
            M.erase( remove_if(M.begin(),M.end(),del),M.end() );
            M.push_back(Rt);
        }
        printf("Top sticks:");
        for(it=M.begin();it!=M.end();++it){
            if(it+1==M.end())
                cout<<' '<<it->k<<'.'<<endl;
            else cout<<' '<<it->k<<',';
        }
    }
    return 0;
}