求助WA 50
查看原帖
求助WA 50
341373
Autofreeze楼主2021/1/16 08:11

RT,样例三输出 41.59

#include<bits/stdc++.h>
#define re register
#define N 501001
#define MAX 2001
#define inf 1e18
#define PI acos(-1)
#define eps 1e-10 
using namespace std;
typedef long long ll;
typedef double db;
inline void read(re ll &ret)
{
	ret=0;re char c=getchar();re bool pd=false;
	while(!isdigit(c)){pd|=c=='-';c=getchar();}
	while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
	ret=pd?-ret:ret;
	return;
}
ll n,tot;
db a,b,r,ans;
struct node
{
	db x,y,theta;	
}w[N],p[N];
ll s[N],head;
inline ll calc(re node a,re node b,re node c,re node d)
{
	return (b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x);
}
inline db dis(re node x,re node y)
{
	return sqrt((y.x-x.x)*(y.x-x.x)+(y.y-x.y)*(y.y-x.y));
}
inline bool cmp(re node x,re node y)
{
	re db tmp=calc(p[1],x,p[1],y);
	if(tmp>0)
		return true;
	else if(tmp==0&&dis(p[1],x)<dis(p[1],y))
		return true;
	else
		return false;
}
signed main()
{
	read(n);
	scanf("%lf %lf %lf",&a,&b,&r);
	a-=2*r;
	b-=2*r;
	re db d=sqrt(a*a/4.0+b*b/4.0);
	ans=2*r*PI;
	for(re int i=1;i<=n;i++)
	{
		scanf("%lf %lf %lf",&w[i].x,&w[i].y,&w[i].theta);
		w[i].theta+=eps;
		w[i].x+=eps;
		w[i].y+=eps;
		re db tmp=atan2(b,a)+w[i].theta;
		p[++tot].x=sin(tmp)*d+w[i].x;
		p[tot].y=cos(tmp)*d+w[i].y;
		tmp=atan2(-b,a)+w[i].theta;
		p[++tot].x=sin(tmp)*d+w[i].x;
		p[tot].y=cos(tmp)*d+w[i].y;
		tmp=atan2(-b,-a)+w[i].theta;
		p[++tot].x=sin(tmp)*d+w[i].x;
		p[tot].y=cos(tmp)*d+w[i].y;
		tmp=atan2(b,-a)+w[i].theta;
		p[++tot].x=sin(tmp)*d+w[i].x;
		p[tot].y=cos(tmp)*d+w[i].y;
	}
	for(re int i=2;i<=tot;i++)
		if(p[i].y<p[1].y||(p[i].y==p[1].y&&p[i].x<p[1].x))
			swap(p[1],p[i]);
	sort(p+2,p+tot+1,cmp);
	s[++head]=1;
	tot++;
	p[tot]=p[1];
	for(re int i=2;i<=tot;i++)
	{
		if(head<2)
		{
			s[++head]=i;
			continue;
		}
		while(head>1&&calc(p[s[head-1]],p[s[head]],p[s[head]],p[i])<=0)
			head--;
		s[++head]=i;
	}
	for(re int i=1;i<head;i++)
		ans+=dis(p[s[i]],p[s[i+1]]);
	printf("%.2lf\n",ans);
	exit(0);
}
2021/1/16 08:11
加载中...