//纯代码
#include<stdio.h>
#define PPmax 30
typedef struct node
{
float x,y;
}Point;
Point DingDian[PPmax];//用于存放凸边形的顶点
int DingDnum=0;
typedef struct Pointss
{
Point p1,p2;
{
min=i;
for(j=i+1;j<=n-1;j++)
{
if( P[j].y < P[min].y )
{
min=j;
}
}
temp=P[i];
P[i]=P[min];
P[min]=temp;
}
return;
}
void Kuaibao(Point P[],int l,int r)
{//P[]:存放点的数组，l,r数组中点起始与终止坐标
//Rtmin,Ltmax用来存放最大最小的t值
float t,Ltmax=0;
Point Pmax;
int Lnum=0;
int LL;
int i,imax;
//连接p[l],p[r]暂时用下面方式实现
printf(" %2d (%.2f,%.2f)--(%.2f,%.2f)",++abc,P[l].x,P[l].y,P[r].x,P[r].y);
Kuaibao(P,r,l);
printf("\n所有边如下：\n");
for(i=0;i<BDDnum;i++)//BDDnum记录已经存入的双点数
{ //BDD[BDDnum]存放凸边形边的双点
printf(" (%.2f,%.2f)--(%.2f,%.2f)\n",BDD[i].p1.x,BDD[i].p1.y,BDD[i].p2.x,BDD[i].p2.y);
// if(t<Ltmax) Ltmax=t; Pmax=p[i];
if(t>Ltmax)
{
Lnum++;
LL=i;
Ltmax=t;
Pmax=P[i];
}
}
if(Lnum>0)
{
printf("\n");
DingDian[DingDnum++]=P[LL];//将P[LL]放入顶点集
Kuaibao(P,l,LL);
P[i]=P[min];
P[min]=temp;
}
//数组两端相同x按|y|排序
//前端排序
px=P[0].x;
pxnum=1;
while(P[pxnum].x==px)
{
pxnum++;
}
for(i=0;i<=pxnum-2;i++)
{
//max=i;
min=i;
for(j=i+1;j<=pxnum-1;j++)
//具体实现：(选择排序实现)
// 1.按x坐标从小到大排
// 2.扫描最前端点元素
// 2.1若不存在相同x坐标的点，则执行3
// 2.2若存在相同x坐标的点，按|y|排列大->小
// 3.扫描最后端点元素
// 3.1若不存在相同x坐标的点，则执行4
// 3.2若存在相同x坐标的点，按|y|排列小->大
i=(l<r)? l:r;
imax=(l>r)? l:r;
for(i=i+1;i<imax;i++)
{
t = P[l].x*P[r].y
+P[i].x*P[l].y
+P[r].x*P[i].y
-P[i].x*P[r].y
-P[r].x*P[l].y
-P[l].x*P[i].y;
//判断t正负，t>0，Lnum++；（Lnum初值为0）
{
if( P[j].y < P[min].y )
{
min=j;
}
}
temp=P[i];
P[i]=P[min];
P[min]=temp;
}
//后端排序
px=P[n-1].x;
pxnum=1;
while(P[n-1-pxnum].x==px)
{
pxnum++;
}
for(i=n-pxnum;i<=n-2;i++)
{
printf(" (%.2f %.2f)\n",P[i].x,P[i].y);
}
l=0;
r=n-1;
//将p[l],p[r]存入顶点集DingDian[]
DingDian[DingDnum++]=P[l];
DingDian[DingDnum++]=P[r];
printf("画边顺序：\n");
Kuaibao(P,l,r);
}
printf("\n");
printf("\n所有顶点如下：\n");
for(i=0;i<DingDnum;i++)
{
printf(" (%.2f,%.2f)\n",DingDian[i].x,DingDian[i].y);
}
return 0;
}
{
int n;
int i;
int l,r;
Point P[PPmax];
printf("输入点的个数：");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%f%f",&P[i].x,&P[i].y);
}
dianxu(P,n);
printf("点序：\n");
for(i=0;i<n;i++)
// 4.返回。
Point temp;
int i,j;
int min,max;
float px;
int pxnum;
//按x坐标排序
for(i=0;i<=n-2;i++)
{
min=i;
for(j=i+1;j<=n-1;j++)
{
if(P[j].x<P[min].x)
{
min=j;
}
}
temp=P[i];
Kuaibao(P,LL,r);
}
else//t=0时，将P[l]、P[r]放入边集
{
printf("\r边--\n");
BDD[BDDnum].p1=P[l];//存放凸边形边的双点
BDD[BDDnum].p2=P[r];
BDDnum++;//记录已经存入的双点数
return;
}
}
int main()
}SDian;
SDian BDD[PPmax];//存放凸边形边的双点
int BDDnum=0;//记录已经存入的双点数
int abc=0;//全局变量，用来记录划边顺序
void dianxu(Point P[],int n)
//对已经输入的点数组进行排序
{//存放点的数组P[],点的个数n
//——点排序