[SHOI2012]信用卡凸包（凸包+直觉）

这个题还是比较有趣。

小心发现，大胆猜想，不用证明！

我们发现所谓的信用卡凸包上弧的长度总和就是圆的周长！

然后再加上每个长宽都减去圆的直径之后的长方形的凸包周长即可！

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=40100;

const double eps=1e-12;

int stack[N],top,n;

double a,b,r,ans;

struct node{

	double x,y;

	node(double xx=0,double yy=0){

		x=xx;y=yy;

	}

}c[N];

node work(node a,double x){

	double A=cos(x),B=sin(x);

	return node(a.x*A-a.y*B,a.x*B+a.y*A);

}

bool cmp(node a,node b){

	if(a.x==b.x)return a.y<b.y;

	else return a.x<b.x;

}

double chaji(node a,node b){

	return a.x*b.y-a.y*b.x;

}

node operator -(node a,node b){

	return node(a.x-b.x,a.y-b.y);

}

node operator +(node a,node b){

	return node(a.x+b.x,a.y+b.y);

}

double dis(node a,node b){

	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

int main(){

	scanf("%d",&n);

	scanf("%lf%lf%lf",&a,&b,&r);

	a-=2.0*r;b-=2.0*r;

	ans=acos(-1.0)*r*2.0;

	for(int i=0;i<n;i++){

		double x,y,z;

		scanf("%lf%lf%lf",&x,&y,&z);

		c[i*4+1].x=b/2.0;c[i*4+1].y=a/2.0;

		c[i*4+1]=work(c[i*4+1],z);c[i*4+1].x+=x;c[i*4+1].y+=y;

		c[i*4+2].x=-b/2.0;c[i*4+2].y=a/2.0;

		c[i*4+2]=work(c[i*4+2],z);c[i*4+2].x+=x;c[i*4+2].y+=y;

		c[i*4+3].x=b/2.0;c[i*4+3].y=-a/2.0;

		c[i*4+3]=work(c[i*4+3],z);c[i*4+3].x+=x;c[i*4+3].y+=y;

		c[i*4+4].x=-b/2.0;c[i*4+4].y=-a/2.0;

		c[i*4+4]=work(c[i*4+4],z);c[i*4+4].x+=x;c[i*4+4].y+=y;

	}

	sort(c+1,c+1+n*4,cmp);

	for(int i=1;i<=n*4;i++){

		if(top<=1){stack[++top]=i;continue;}

		while(top>=2&&chaji(c[stack[top]]-c[stack[top-1]],c[i]-c[stack[top]])+eps<0)top--;

		stack[++top]=i;

	}

	for(int i=1;i<top;i++)ans+=dis(c[stack[i]],c[stack[i+1]]);

	top=0;

	for(int i=n*4;i>=1;i--){

		if(top<=1){stack[++top]=i;continue;}

		while(top>=2&&chaji(c[stack[top]]-c[stack[top-1]],c[i]-c[stack[top]])+eps<0)top--;

		stack[++top]=i;

	}

	for(int i=1;i<top;i++)ans+=dis(c[stack[i]],c[stack[i+1]]);

	printf("%.2lf",ans);

	return 0;

}

巴特西

[SHOI2012]信用卡凸包（凸包+直觉）

最新文章

热门文章