萌新OI3s求助:关于O2
查看原帖
萌新OI3s求助:关于O2
261046
Cht_master楼主2021/9/2 21:43

rt,开了O2全部RE。

#include<bits/stdc++.h>
#define db double
using namespace std;
const int mxN(1e5);
struct P{db x,y;};
struct Vec{db x,y;};
namespace Basic{
	db sqr(db x){return x*x;}
	db dist(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
	db Cross(Vec a,Vec b){return a.x*b.y-a.y*b.x;}//叉积(a->b向左转为正).
	Vec vec(P a,P b){Vec A;A.x=b.x-a.x,A.y=b.y-a.y;return A;}
	db check(P a,P b,P c){
		Vec ab(vec(a,b)),bc(vec(b,c));
		return Cross(ab,bc);
	}
}
namespace Stack{
	P st[mxN+5];int top;
	void psh(P a){st[++top]=a;}
	void pop(){if(top>=1)--top;}
	P Top(){return st[top];}
	P TTop(){return st[top-1];}
}
namespace Cvx{
	using namespace Basic;
	using namespace Stack;
	int n;P p[mxN+5];db C;
	bool cmp(P a,P b){
		if(a.x==b.x)return a.y<b.y;
		return a.x<b.x;
	}
	void init(){
		scanf("%d",&n);
		for(int i(1);i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);
	}
	db calC(){
    //在这里写exit(0)是不会RE的.
		C=0;
		for(int i(1);i<=top-1;++i)C+=dist(st[i],st[i+1]);
    //在这里写exit(0)就会RE.说明是上面这个for的问题.但是这也能有问题???.
	}
	int uniq(P p[],int l,int r){
		int end(r);
		for(int i(l+1);i<=end;++i)
			if(p[i].x==p[i-1].x&&p[i].y==p[i-1].y)swap(p[i],p[end--]);
		return end;
	}
	void Andrew(){
		init();
		if(n==1){C=0;return;}
		if(n==2){C=dist(p[1],p[2]);return;}
		sort(p+1,p+n+1,cmp),n=uniq(p,1,n);
		psh(p[1]),psh(p[2]);
		for(int i(3);i<=n;++i){//p1开始的下凸包.
			while(top>1&&check(TTop(),Top(),p[i])<=0)pop();
			//1.细节top>1!!!因为第一个点不能出栈!!!;
			//2.向右转会更劣(<=0为向右).
			psh(p[i]);
		}
		int tp(top);
		for(int i(n-1);i>=1;--i){//pn开始的上凸包.
			while(top>tp&&check(TTop(),Top(),p[i])<=0)pop();
			//3.同理:top>tp(严格大于!!!).
			psh(p[i]);
		}
		//上面已经再次入栈p[1],不用再单独入栈.
		calC();
	}
}
int main(){
	Cvx::Andrew(),printf("%.2lf",Cvx::C);
	return 0;
}
2021/9/2 21:43
加载中...