C++程序设计：挑棍子（判断线段是否相交的模板）

我就是我 2022-12-02 13:56 138阅读 0赞

**【问题描述】**

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70_pic_center]

**【输入形式】**

输入由若干测试用例组成，每个用例以一个整数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

**【题解】**

判断线段是否相交的方法：

>  *  基于向量叉积  
>     参考[此链接][Link 1]。
>  *  基于直线方程  
>     取两条线段对应的直线方程（两点式），联立求交点坐标。之后判断交点坐标（x或y均可）是否在线段范围上即可。

#include <iostream>
    #include <cmath>
    using namespace std;
    struct sticks { 
    	float x1,x2,y1,y2;
    	float k;//斜率 
    	bool banana;
    };
    //判断两根线段是否相交 
    bool judge(sticks s1,sticks s2) { 
    	if(s1.k==s2.k)
    		return false;
    	double banana=(s1.k*s1.x1-s2.k*s2.x1+s2.y1-s1.y1)/(s1.k-s2.k);
    	return (banana>max(s1.x1,s2.x1)&&banana<min(s1.x2,s2.x2))?true:false;
    }
    int main() { 
    	int n=1,i,j,count;
    	sticks stick[1000];
    	int answer[100][100];
    	for(count=0; n!=0; count++) { 
    		for(int m=0; m<1000; m++)
    			stick[m].banana=true;
    		cin>>n;
    		for(i=0; i<n; i++) { 
    			cin>>stick[i].x1>>stick[i].y1>>stick[i].x2>>stick[i].y2;
    			stick[i].k=(stick[i].y1-stick[i].y2)/(stick[i].x1-stick[i].x2);
    		}
    		for(i=n-2; i>=0; i--) { 
    			for(j=i+1; j<n; j++) { 
    				if(judge(stick[i],stick[j])==true) { 
    					stick[i].banana=false;
    					break;
    				}
    			}
    		}
    		int time=0;
    		for(i=0; i<n; i++) { 
    			if(stick[i].banana==true) { 
    				answer[count][time]=i+1;
    				time++;
    			}
    		}
    	}
    	for(i=0; i<count-1; i++) { 
    		cout<<"Top sticks: "<<answer[i][0];
    		j=1;
    		while(answer[i][j]!=0) { 
    			cout<<","<<answer[i][j];
    			j++;
    		}
    		cout<<endl;
    	}
    	return 0;
    }

判断线段是否相交的模板：

bool judge(sticks s1,sticks s2) { 
    	if(s1.k==s2.k)
    		return false;
    	double banana=(s1.k*s1.x1-s2.k*s2.x1+s2.y1-s1.y1)/(s1.k-s2.k);
    	return (banana>max(s1.x1,s2.x1)&&banana<min(s1.x2,s2.x2))?true:false;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d000d116a7f04877a0ee21c1e4d3b7e9.png
[Link 1]: https://www.cnblogs.com/tuyang1129/p/9390376.html