频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 2653 Pick-up sticks--线段相交--vector
2012-08-15 09:25:16           
收藏   我要投稿
[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
点击复制链接 与好友分享!回本站首页
相关TAG标签 线段
上一篇: poj 3581 Sequence
下一篇:HDU 1166 敌兵布阵
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站