大家都很强， 可与之共勉 。

题意：
  给定一个规模的矩形，长为$a$，宽为$b$，其中它的四个角是一个半径为$r$的$\frac{1}{4}$圆。给您$n$个这样的图形，以$x,y,\theta$这样的三元组给出，表示其中心坐标（对角线交点），相对于$x$正半轴的逆时针旋转角度。

  问您这个图形的凸包周长是多少，保留两位小数。
其中n≤10000，0.1≤a,b≤1000000.0，0.0≤r<min(a4,b4)，|x|,|y|≤1000000.0，0≤θ<2π。$n\leq10000，0.1 \leq a, b \leq 1000000.0， 0.0 ≤ r < min(\frac{a}{4}, \frac{b}{4})，|x|, |y| ≤ 1000000.0， 0 ≤ \theta < 2π。$

题解：

  把所有矩形（未进行圆滑处理）的顶点找出，然后直接找凸包，最后加上一个圆的周长。因为凸包是凸多边形，内角和是$2\pi$。所以这个做法具有正确性。

  那么问题就在于如何找顶点（顺便吐槽网上的做法劳资看不懂），用到向量的旋转。

  （没有画图工具……）
  设要旋转的向量为$z$，建系化为基底表示为$(x,y)$，设旋转后的向量为$z'$。设$z$与$x$正半轴的夹角为$\alpha$，旋转角度为$\beta$。

  可以知道的是，旋转前后模长不变，设为$r$。
于是原来向量的坐标可以表示为$(r\cdot cos\alpha,r\cdot sin\alpha)$
  旋转后的向量可以表示为$(r\cdot cos(\alpha+\beta),r\cdot sin(\alpha+\beta))$

  由和角公式

$$z'=(r\cdot(cos\alpha \cdot \cos\beta-sin\alpha \cdot \sin\beta),r\cdot(sin\alpha \cdot \cos\beta+sin\beta \cdot \cos\alpha))$$
$$z'=(r\cdot cos\alpha \cdot \cos\beta-r\cdot sin\alpha \cdot \sin\beta,r\cdot sin\alpha \cdot \cos\beta+r\cdot sin\beta \cdot \cos\alpha))$$

因为

$$x=r\cdot cos\alpha,y=r\cdot sin\alpha$$
所以
$$z'=(x \cdot \cos\beta-y \cdot \sin\beta,y \cdot \cos\beta+x \cdot \sin\beta))$$

然后就很简单了……

（话说突然发现自己凸包的板子有一步多余了）

/**************************************************************Problem: 2829User: Lazer2001Language: C++Result: AcceptedTime:108 msMemory:13804 kb
****************************************************************/# include const double eps = 1e-8 ;
const double Pi = acos ( -1 ) ;inline int dcmp ( double x )  {return ( x > -eps ) - ( x < eps ) ;
}typedef struct Vector  {double x, y ;Vector ( )  {   }Vector ( double x, double y ) : x ( x ), y ( y )  {     }inline Vector operator - ( const Vector& rhs )  const  {return Vector ( x - rhs.x, y - rhs.y ) ;}inline Vector operator + ( const Vector& rhs )  const  {return Vector ( x + rhs.x, y + rhs.y ) ;}inline double operator % ( const Vector& rhs )  const  {return x * rhs.y - y * rhs.x ;}
}  Vector, Point ;struct Pcmp  {inline bool operator ( ) ( const Point& a, const Point& b ) const {return ( a.x == b.x ) ? a.y < b.y : a.x < b.x ;}
} ;int Graham ( Point* p, int n, Point* res )  {std :: sort ( p, p + n, Pcmp ( ) ) ;register int tp ( 1 ) ;for ( int i = 0 ; i < 2 ; ++ i )  res [i] = p [i] ;for ( int i = 2 ; i < n ; ++ i )  {while ( tp && dcmp ( ( p [i] - res [tp - 1] ) % ( res [tp] - res [tp - 1] ) ) >= 0 )  -- tp ;res [++ tp] = p [i] ;}int len = tp ;res [++ tp] = p [n - 2] ;for ( int i = n - 3 ; i >= 0 ; -- i )  {while ( tp != len && dcmp ( ( p [i] - res [tp - 1] ) % ( res [tp] - res [tp - 1] ) ) >= 0 )  -- tp ;res [++ tp] = p [i] ;}return tp ;
}# define N 400010Point p [N], con [N] ;# undef Ninline Point Rotate ( Point a, double rad )  {  return Point ( a.x * cos ( rad ) - a.y * sin ( rad ), a.y * cos ( rad ) + a.x * sin ( rad ) ) ;  
}int main ( )  {int n ;scanf ( "%d", & n ) ;double a, b, r ;scanf ( "%lf%lf%lf", & a, & b, & r ) ;a -= 2 * r, b -= 2 * r ;int cnt ( 0 ) ;while ( n -- )  {static double x, y, angle ;scanf ( "%lf%lf%lf", & x, & y, & angle ) ;Vector cur = Vector ( x, y ) ;p [cnt ++] = cur + Rotate ( Vector ( b / 2, a / 2 ), angle ) ;p [cnt ++] = cur + Rotate ( Vector ( - b / 2, a / 2 ), angle ) ;p [cnt ++] = cur + Rotate ( Vector ( b / 2, - a / 2 ), angle ) ;p [cnt ++] = cur + Rotate ( Vector ( - b / 2, - a / 2 ), angle ) ;}int ccnt = Graham ( p, cnt, con ) ;con [ccnt] = con [0] ;double ans ( 0 ) ;for ( int i = 0 ; i < ccnt ; ++ i )  {ans += hypot ( con [i].x - con [i + 1].x, con [i].y - con [i + 1].y ) ;}printf ( "%.2lf\n", ans + 2 * r * Pi ) ;return 0 ;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！