过了,但是过不了样例,求问为什么
查看原帖
过了,但是过不了样例,求问为什么
371780
dsy081101楼主2024/1/23 13:11

当时没有计算几何的基础,完全yy的解法,但是能过所有数据却过不了样例,有点怪,是样例其实是一种特殊情况吗(),那么这种东西要怎么改才能过阳历呢

#include <bits/stdc++.h>
// #define _int __int 128
using namespace std;
#define int long long
#define x first
#define y second
#define iter map<int,int>::iterator
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace Mine{
	mt19937_64 wql(1145141919810);
	inline ll read(){
		ll x=1,a=0;
		char ch=getchar();
		while(ch>'9' || ch<'0')x=(ch=='-')?-1:x,ch=getchar();
		while(ch>='0' && ch<='9')
			a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
		return a*x;
	}
	const int N=1e5+100;
	int cmp(double ax,double ay,double bx,double by,double cx,double cy){
		double tmp=(bx-ax)*(cy-by)-(by-ay)*(cx-bx);
		if(tmp>0) return 1;
		if(tmp<0) return -1;
		return 0;
	}
	struct point{
		double x,y;
	}a[N];
	int cmp(point a,point b,point c){
		return cmp(a.x,a.y,b.x,b.y,c.x,c.y);
	}
	int n;
	int up[N],tup,down[N],tdown;
	double dist(point a,point b){
		return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
	}
	signed main(){
		n=read();
		for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
		sort(a+1,a+1+n,[](point x,point y){return (x.x!=y.x)?x.x<y.x:x.y<y.y;});
		double ans=0;
		down[++tdown]=1;
		for(int i=2;i<=n;i++){
			// cout<<a[i].x<<" "<<a[i].y<<endl;
			// if(fabs(a[down[tdown]].x-a[i].x)<1e-6){
				// (a[down[tdown]].y>a[i].y) continue;
				// down[++tdown]
			// }
			while(tdown>1 && cmp(a[down[tdown]],a[down[tdown-1]],a[i])>=0) tdown--;
			down[++tdown]=i;
		}
		sort(a+1,a+1+n,[](point x,point y){return (x.x!=y.x)?x.x<y.x:x.y>y.y;});
		up[++tup]=n;
		for(int i=n-1;i>=1;i--){
			// if(fabs(a[up[tup]].x-a[i].x)<1e-6){
				// if(a[up[tup]].y<a[i].y) up[tup]=i;
				// continue;
			// }
			while(tup>1 && cmp(a[up[tup]],a[up[tup-1]],a[i])>=0) tup--;
			up[++tup]=i;
		}
		// for(int i=1;i<=tup;i++){
			// cout<<a[up[i]].x<<" "<<a[up[i]].y<<endl;
		// }
		for(int i=2;i<=tup;i++){
			// cout<<a[up[i]].y<<endl;
			ans+=dist(a[up[i-1]],a[up[i]]);
		}
		for(int i=2;i<=tdown;i++){
			ans+=dist(a[down[i-1]],a[down[i]]);
		}
		printf("%.2lf",ans);
		return 0;
	}
}
signed main(){
	 // freopen("wu.in","r",stdin);
	 // freopen("wu.out","w",stdout);
	return Mine::main();
}
2024/1/23 13:11
加载中...