有何不同???
查看原帖
有何不同???
977139
fanyixuan1010楼主2024/9/14 18:41
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int eps=1e-6;
int sgn(double x){
	if(fabs(x)<eps)return 0;
	else return x<0?-1:1;
}
struct P{
	double x,y;
	P(){}
	P(double x,double y):x(x),y(y){}
	bool operator<(P u){return sgn(x-u.x)<0||(sgn(x-u.x)==0&&sgn(y-u.y)<0);}
	bool operator==(P u){return sgn(x-u.x)==0&&sgn(y-u.y)==0;}
	P operator-(P u){return P(x-u.x,y-u.y);}
}p[N],q[N];
double cross(P a,P b){return a.x*b.y-a.y*b.x;}//|a||b|sin(B-A)
double dis(P a,P b){return hypot(a.x-b.x,a.y-b.y);}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
	n=unique(&p[1],&p[n]+1)-p-1;
	sort(&p[1],&p[n]+1);
	int v=0;
	for(int i=1;i<=n;i++){
		while(v>1&&sgn(cross(q[v-1]-q[v-2],p[i]-q[v-1]))<=0)v--;
		q[v++]=p[i];
	}
	int j=v;
	for(int i=n-1;i>=1;i--){
		while(v>j&&sgn(cross(q[v-1]-q[v-2],p[i]-q[v-1]))<=0)v--;
		q[v++]=p[i];
	}
	double ans=0;
	for(int i=0;i<v;i++){
		ans+=dis(q[i],q[(i+1)%v]);
	}
	printf("%.2f",ans);
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
const double eps = 1e-6;
int sgn(double x){        //判断x是否等于0
	if(fabs(x) < eps)  return 0;
	else return x<0?-1:1;
}
struct Point{
	double x,y;
	Point(){}
	Point(double x, double y):x(x),y(y){}
	Point operator + (Point B){return Point(x+B.x,y+B.y);}
	Point operator - (Point B){return Point(x-B.x,y-B.y);}
	bool operator == (Point B){return sgn(x-B.x) == 0 && sgn(y-B.y) == 0;}
	bool operator < (Point B){                  //用于sort()排序,先按x排序,再按y排序
		return sgn(x-B.x)<0 || (sgn(x-B.x)==0 && sgn(y-B.y)<0);}
};
typedef Point Vector;
double Cross(Vector A,Vector B){return A.x*B.y - A.y*B.x;}      //叉积
double Distance(Point A,Point B){return hypot(A.x-B.x,A.y-B.y);}
//Convex_hull()求凸包。凸包顶点放在ch中,返回值是凸包的顶点数
int Convex_hull(Point *p,int n,Point *ch){
	n = unique(p,p+n)-p;    //去除重复点    
	sort(p,p+n);            //对点排序:按x从小到大排序,如果x相同,按y排序    
	int v=0;
	//求下凸包。如果p[i]是右拐弯的,这个点不在凸包上,往回退
	for(int i=0;i<n;i++){
		while(v>1 && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0) //把后面ch[v-1]改成ch[v-2]也行
			v--;
		ch[v++]=p[i];
	}
	int j=v;
	//求上凸包
	for(int i=n-2;i>=0;i--){
		while(v>j && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0) //把后面ch[v-1]改成ch[v-2]也行
			v--;
		ch[v++]=p[i];
	}
	if(n>1) v--;
	return v;                      //返回值v是凸包的顶点数
}
Point p[N],ch[N];                  //输入点是p[],计算得到的凸包顶点放在ch[]中
int main(){
	int n;   cin >> n;
	for(int i=0;i<n;i++)  scanf("%lf%lf",&p[i].x,&p[i].y);
	int v = Convex_hull(p,n,ch);    //返回凸包的顶点数v
	double ans=0;
	for(int i=0;i<v;i++)  ans += Distance(ch[i],ch[(i+1)%v]);  //计算凸包周长
	printf("%.2f\n",ans);
	return 0;
}

两份代码有何不同???

2024/9/14 18:41
加载中...