棍子"/>
挑棍子
【问题描述】
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
1 | : | #include<iostream> |
2 | : | using namespace std; |
3 | 1 : | int main() |
4 | : | { |
5 | : | int n,i,j; |
6 | 1 : | int x1,x2,x3,x4,y1,y2,y3,y4,shuchu[100]={0},s=0; |
7 | : | bool xiangjiao(int,int,int,int,float,float,int,int); |
8 | 1 : | float z[100][5]={0},k1,k2; |
9 | : | for(;;){ |
10 | 3 : | cin>>n; |
11 | 3 : | if(n==0) break; |
12 | 10 : | for(i=0;i<n;i++) |
13 | 40 : | for(j=0;j<4;j++) |
14 | 32 : | cin>>z[i][j]; |
15 | 8 : | for(i=0;i<n-1;i++){ |
16 | 6 : | x1=z[i][0];y1=z[i][1]; |
17 | 6 : | x2=z[i][2];y2=z[i][3]; |
18 | 6 : | k1=(y1-y2)*1.0/(x1-x2); |
19 | 13 : | for(j=i+1;j<n;j++){ |
20 | 9 : | x3=z[j][0];y3=z[j][1]; |
21 | 9 : | x4=z[j][2];y4=z[j][3]; |
22 | 9 : | k2=(y3-y4)*1.0/(x3-x4); |
23 | 9 : | z[i][4]=xiangjiao(x1,y1,x3,y3,k1,k2,x2,x4); |
24 | 9 : | if(z[i][4]==1) break; |
25 | : | } |
26 | : | } |
27 | 10 : | for(i=0;i<n;i++){ |
28 | 8 : | if(z[i][4]==0){ |
29 | 6 : | shuchu[s]=i+1; |
30 | 6 : | s++; |
31 | : | } |
32 | : | } |
33 | 2 : | cout<<"Top sticks: "; |
34 | 8 : | for(i=0;i<s;i++){ |
35 | 6 : | if(i==s-1) cout<<shuchu[i]<<endl; |
36 | 4 : | else cout<<shuchu[i]<<','; |
37 | : | } |
38 | 2 : | s=0; |
39 | 10 : | for(i=0;i<n;i++){ |
40 | 8 : | z[i][4]=0; |
41 | : | } |
42 | 2 : | } |
43 | 1 : | } |
44 | 9 : | bool xiangjiao(int x1,int y1,int x3,int y3,float k1,float k2,int x2,int x4) |
45 | : | { |
46 | : | float x; |
47 | 9 : | x=(k1*x1-y1-k2*x3+y3)/(k1-k2); |
48 | 9 : | if(x>=x1&&x<=x2&&x>=x3&&x<=x4) return 1; |
49 | 7 : | else return 0; |
50 | 3 : | } |
更多推荐
挑棍子
发布评论