题目描述

输入

输出

样例输入

2

6.0 2.0 0.0

0.0 0.0 0.0

2.0 -2.0 1.5707963268

样例输出

21.66

---

题解

凸包

傻逼题，答案显然为：所有圆心构成的凸包周长+一个圆的周长。这里求凸包用的方法是求上下两个凸壳再拼起来。

时间复杂度为排序的 $O(n\log n)$ 

我才不会告诉你puts("nan:)可以过呢

#include 
     
      #include 
      
       #include 
       
        using namespace std;const double pi = acos(-1);struct data{	double x , y;	data() {}	data(double a , double b) {x = a , y = b;}	data operator-(const data &a)const {return data(x - a.x , y - a.y);}	double operator*(const data &a)const {return x * a.y - y * a.x;}	bool operator<(const data &a)const {return x == a.x ? y < a.y : x < a.x;}}p[40010] , sa[40010] , sb[40010];int ta , tb;inline double dis(data a , data b){	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}int main(){	int n , i , m = 0;	double a , b , r , x , y , c , ans = 0;	scanf("%d%lf%lf%lf" , &n , &a , &b , &r) , a = a / 2 - r , b = b / 2 - r;	for(i = 1 ; i <= n ; i ++ )	{		scanf("%lf%lf%lf" , &x , &y , &c);		p[++m] = data(x + b * cos(c) + a * sin(c) , y + b * sin(c) - a * cos(c));		p[++m] = data(x - b * cos(c) + a * sin(c) , y - b * sin(c) - a * cos(c));		p[++m] = data(x + b * cos(c) - a * sin(c) , y + b * sin(c) + a * cos(c));		p[++m] = data(x - b * cos(c) - a * sin(c) , y - b * sin(c) + a * cos(c));	}	sort(p + 1 , p + m + 1);	for(i = 1 ; i <= m ; i ++ )	{		while(ta > 1 && (p[i] - sa[ta]) * (sa[ta - 1] - sa[ta]) >= 0) ta -- ;		while(tb > 1 && (p[i] - sb[tb]) * (sb[tb - 1] - sb[tb]) <= 0) tb -- ;		sa[++ta] = sb[++tb] = p[i];	}	for(i = 1 ; i < ta ; i ++ ) ans += dis(sa[i] , sa[i + 1]);	for(i = 1 ; i < tb ; i ++ ) ans += dis(sb[i] , sb[i + 1]);	printf("%.2lf\n" , ans + dis(sa[1] , sb[1]) + dis(sa[ta] , sb[tb]) + 2 * pi * r);	return 0;}