首页 » C++ » 挑棍子

挑棍子

原文 http://blog.csdn.net/secular_/article/details/79192629

2018-01-30 02:00:47阅读(566)

Stan有n根不同长度的棍子。他随机地一次性将它们扔到地上,扔完后,Stan想找到那些顶层的棍子,也就是那些没有其他棍子压在上面的棍子。他注意到最后扔的棍子总是顶层的,而他想知道所有顶层的棍子。棍子非常非常薄,其厚度可以忽略。

挑棍子

【输入形式】

   输入由若干测试用例组成,每个用例以一个整数n(1<=n<=100000)开始,表示棍子数。每个用例接下来的n行包含4个数,表示棍子端点的平面坐标,以Stan扔出的棍子的顺序列出。假定不超过1000根顶层棍子,n=0表示输入结束。

【输出形式】

  对于每个输入用例,按照样例格式列出顶层棍子。顶层棍子按照扔出的顺序列出,图片对应输入中的第一个用例。

【样例输入】

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
【样例输出】

Top sticks: 2,4,5
Top sticks: 1,2,3
【样例说明】提示:利用向量叉积判断线段是否相交。
【评分标准】

#include<iostream>
#include<vector>
using namespace std;
float jiaodian(float k1,float b1,float k2,float b2){
    float x=(b2-b1)/(k1-k2);
    return x;
}
int main(){
    int n;
    while(1){
        cin>>n;
        if(n==0)
        break;
        else{
            float a[n][4];//存顶点 
    float b[n][2];//存k、b 
    int c[n];//标志是否在上面; 
    for(int i=0;i<n;i++){
        c[i]=1; //初始化情况为都在最上面 
        for(int j=0;j<4;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        float x1=a[i][0];
        float y1=a[i][1];
        float x2=a[i][2];
        float y2=a[i][3];
        b[i][0]=(y1-y2)/(x1-x2);
        b[i][1]=(x1*y2-x2*y1)/(x1-x2);
    } 
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<n;j++){
        float x=jiaodian(b[i][0],b[i][1],b[j][0],b[j][1]);
            if(x>=a[i][0]&&x<=a[i][2]&&x>=a[j][0]&&x<=a[j][2])
            c[i]=0;
        }
    }
    cout<<"Top sticks: ";
    vector<int> m;int ss=0;
    for(int i=0;i<n;i++){
        if(c[i]==1)
        {
        m.push_back(i+1);ss++;  
        }   
    }
    for(int i=0;i<ss;i++){
        cout<<m[i];
        if(i!=ss-1)
        cout<<",";
    }
    cout<<endl; 
        }
    }   
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹