POJ 2007(卷包裹算法(Gift Wrapping Algorithm)+ostream)
发布时间：2022-11-08 02:14:27 279 相关标签： # ios
注意istream和ostream的写法
它必须是友元函数（如果是成员函数，则必须以const P为开头，这显然不行）
它返回一个指向ostream的指针，前面可以接ostream(cout<)，还有一个元素（要输入的）
friend ostream& operator<<(ostream& cout,P &a)
{
cout<<"("<return cout;
}接下来讲卷包裹算法：
我们先找到一个在凸包上的点，然后卷过去
伪代码如下：
初始化st[]=0,j=0,endpoint=P0
do
{
将endpoint加入队列st.
找到任意从P0点出发，转向最右的点P
endpoint=P
}until endpoint=P0
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (50+10)
struct P
{
int x,y;
P(){}
P(int _x,int _y):x(_x),y(_y){}
friend ostream& operator<<(ostream& cout,P &a)
{
cout<<"("< return cout;
}
}a[MAXN];
struct V
{
int x,y;
V(){}
V(int _x,int _y):x(_x),y(_y){}
V(P A,P B):x(B.x-A.x),y(B.y-A.y){}
};
int operator*(V a,V b)
{
return a.x*b.y-a.y*b.x;
}
int n,st[MAXN];
int main()
{
// freopen("poj2007.in","r",stdin);
int n=1;
while (scanf("%d%d",&a[n].x,&a[n].y)!=-1) n++; //scanf读入失败返回-1
n--;
int endpoint=1,j=1;
do
{
cout< int k=(endpoint+1)%n+1;
for (int i=1;i<=n;i++)
if (endpoint!=i&&V(a[endpoint],a[i])*V(a[endpoint],a[k])>0) k=i;
endpoint=k;
// cout< }while (endpoint!=1);
return 0;
}
文章来源： https://blog.51cto.com/u_15724837/5820816
特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。
举报
