计算机和求救
查看原帖
计算机和求救
390770
D2T1xubiaoshi楼主2021/1/22 17:13
//P2742
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=100005;
const double minim=0.00000001;
struct point{double x,y;}p[maxn],s[maxn],t;
double ans;
int n,top;

double cross(point p,point p1,point p2){
	double x1,y1,x2,y2;
	x1=p1.x-p.x;
	y1=p1.y-p.y;
	x2=p2.x-p.x;
	y2=p2.y-p.y;
	return (abs(x1*y2-x2*y1)<minim ? 0 : x1*y2-x2*y1);
}
double dis(point p1,point p2){
	double px,py;
	px=abs(p1.x-p2.x);
	py=abs(p1.y-p2.y); 
	return sqrt(px*px+py*py);
}
bool cmp(point p1,point p2){
	double c=cross(p[1],p1,p2);
	if(c<0) return false;
	if(c-0<minim && dis(p[1],p1)>dis(p[1],p2)) return false;
	return false;
}
void graham(){
	sort(p+1+1,p+n+1,cmp);
	s[1]=p[1],s[2]=p[2],++n,p[n]=p[1];
	top=2;
	for(int i=3; i<=n; ++i){
		while(top>1 && cross(s[top-1],s[top],p[i])<=0) --top;
		s[++top]=p[i];
	}
	return;
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; ++i){
		scanf("%lf %lf",&p[i].x,&p[i].y);
		if((p[i].y<p[1].y && abs(p[i].y-p[1].y)<minim) || (abs(p[i].y-p[1].y)<minim && p[i].x<p[1].x))
			t=p[i],p[i]=p[1],p[1]=p[i];
	}
	graham();
	for(int i=2; i<=top; ++i)
		ans+=dis(s[i],s[i-1]);
	printf("%.2lf",ans);
	return 0;
}

0pts

但是有的数据能过

2021/1/22 17:13
加载中...