【bzoj2829】信用卡凸包 凸包

题目描述

输入

输出

样例输入

2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268

样例输出

21.66

---

题解

凸包

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

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

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

#include <cmath>
#include <cstdio>
#include <algorithm>
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
" , ans + dis(sa[1] , sb[1]) + dis(sa[ta] , sb[tb]) + 2 * pi * r);
	return 0;
}