求助!!!只AC了第一个点
查看原帖
求助!!!只AC了第一个点
317859
wangjingjie2022楼主2020/6/7 15:59
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100005;
struct point{
	double x,y;
}a[maxn],sum[maxn];
int n,cnt=1;
double ans;
double check(point x1,point x2,point y1,point y2){
	return (x2.x-x1.x)*(y2.y-y1.y)-(y2.x-y1.x)*(x2.y-x1.y);
}
double len(point x,point y){
	return sqrt((y.x-x.x)*(y.x-x.x)+(y.y-x.y)*(y.y-x.y));
}
bool cmp(point p1,point p2){
	double temp=check(a[1],p1,a[1],p2);
	if(temp>0||temp==0&&len(a[0],p1)<len(a[0],p2))return 1;
	return 0;
}
void swpa(point x,point y){
	point t=x;
	x=y;
	y=t;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&a[i].x,&a[i].y);
		if(i!=1&&a[i].y<a[1].y)swpa(a[1],a[i]);
	}
	sort(a+2,a+n+1,cmp);
	sum[1]=a[1];
	for(int i=2;i<=n;i++){
		while(cnt>1&&check(sum[cnt-1],sum[cnt],sum[cnt],a[i])<=0)--cnt;
		sum[++cnt]=a[i];
	}
	sum[cnt+1]=a[1];
	for(int i=1;i<=cnt;i++)ans+=len(sum[i],sum[i+1]);
	printf("%.2lf\n",ans);
	return 0;
}
2020/6/7 15:59
加载中...