poj 2653 Pick-up sticks--線段相交--vector

[cpp]
/*
題意：隨即扔一些棒子，輸出在最上面的棒子(沒有那個棒子壓著它)的編號
 
線段相交問題
 
本體用到了  vector    
注意    v.erase(remove_if(v.begin(),v.end(),ok),v.end());  用法
同時    v.erase  返回的是刪除過後，下一個元素的位置，不要再for裡面用 it++  在循環裡面自己操作
*/ 
#include<stdio.h>  
#include<vector>  
#include<algorithm>  
using namespace std; 
const double esp=1e-8; 
struct point 
{ 
    double x,y; 
};  
struct node 
{ 
    point p1,p2; 
    int no; 
}; 
vector<node>v; 
int n; 
node cc; 
double max(double a,double b){return a>b?a:b;} 
double min(double a,double b){return a<b?a:b;} 
double cross(point p,point s,point e) 
{ 
    return (e.x-s.x)*(p.y-s.y)-(p.x-s.x)*(e.y-s.y); 
} 
bool segintersect(point s1,point e1,point s2,point e2) 
{ 
    return((max(s1.x,e1.x)>=min(s2.x,e2.x))&& 
        (max(s2.x,e2.x)>=min(s1.x,e1.x))&& 
        (max(s1.y,e1.y)>=min(s2.y,e2.y))&& 
        (max(s2.y,e2.y)>=min(s1.y,e1.y))&& 
        (cross(s1,s2,e2)*cross(e1,s2,e2)<=esp)&& 
        (cross(s2,s1,e1)*cross(e2,s1,e1)<=esp));  
} 
bool ok(node n) 
{ 
    if(segintersect(n.p1,n.p2,cc.p1,cc.p2)) 
        return true; 
    return false; 
} 
int main() 
{ 
    int i; 
    while(scanf("%d",&n),n) 
    { 
        v.erase(v.begin(),v.end()); 
        for(i=1;i<=n;i++) 
        { 
            scanf("%lf%lf%lf%lf",&cc.p1.x,&cc.p1.y,&cc.p2.x,&cc.p2.y); 
            cc.no=i; 
            v.erase(remove_if(v.begin(),v.end(),ok),v.end()); 
            v.push_back(cc); 
        } 
        printf("Top sticks: "); 
        for(vector<node>::iterator it = v.begin(); it!= v.end(); it++) 
        { 
            printf("%d",it->no); 
            if(it!=v.end()-1) 
                printf(", "); 
            else printf(".\n"); 
        } 
    } www.2cto.com
    return 0; 
} 

作者：qq172108805