2829: 信用卡凸包
Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge
Submit: 327 Solved: 151
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268
Sample Output
21.66
HINT
本樣例中的2張信用卡的輪廓在上圖中用實線标出，如果視1.5707963268為
Pi/2(pi為圓周率),則其凸包的周長為16+4*sqrt(2)
Source
[ Submit][ Status][ Discuss]
題解：凸包
以圓心為點做凸包，然後求凸包的周長，最後加上一個圓的周長。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100003
using namespace std;
int n,m;
double a,b,r,pi=acos(-1.0);
struct vector{
double x,y;
vector(double X=0,double Y=0) {
x=X,y=Y;
}
}p[N],ch[N];
bool operator <(vector a,vector b)
{
return a.x<b.x||a.x==b.x&&a.y<b.y;
}
vector operator +(vector a,vector b){
return vector (a.x+b.x,a.y+b.y);
}
vector operator -(vector a,vector b){
return vector (a.x-b.x,a.y-b.y);
}
vector operator *(vector a,double k){
return vector (a.x*k,a.y*k);
}
vector rotate(vector a,double rad)
{
return vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
double cross(vector a,vector b){
return a.x*b.y-a.y*b.x;
}
double get_len(vector a){
return sqrt(a.x*a.x+a.y*a.y);
}
void convexhull()
{
sort(p+1,p+n+1);
m=0;
for (int i=1;i<=n;i++) {
while (m>1&&cross(ch[m]-ch[m-1],p[i]-ch[m])<0) m--;
ch[++m]=p[i];
}
int k=m;
for (int i=n;i>=1;i--) {
while (m>k&&cross(ch[m]-ch[m-1],p[i]-ch[m])<0) m--;
ch[++m]=p[i];
}
m--;
}
int main()
{
freopen("a.in","r",stdin);
freopen("my.out","w",stdout);
scanf("%d",&n);
scanf("%lf%lf%lf",&a,&b,&r);
int cnt=0;
for (int i=1;i<=n;i++) {
double x,y,rad;
scanf("%lf%lf%lf",&x,&y,&rad);
double l=a-2.0*r; l/=2.0;
double d=b-2.0*r; d/=2.0; vector v;
p[0]=vector(x,y);
p[++cnt].x=x+d; p[cnt].y=y+l; v=rotate(p[cnt]-p[0],rad); p[cnt]=p[0]+v;
p[++cnt].x=x-d; p[cnt].y=y-l; v=rotate(p[cnt]-p[0],rad); p[cnt]=p[0]+v;
p[++cnt].x=x+d; p[cnt].y=y-l; v=rotate(p[cnt]-p[0],rad); p[cnt]=p[0]+v;
p[++cnt].x=x-d; p[cnt].y=y+l; v=rotate(p[cnt]-p[0],rad); p[cnt]=p[0]+v;
// for (int j=cnt;j>=cnt-4+1;j--)
// cout<<p[j].x<<" "<<p[j].y<<endl;
}
n=cnt;
convexhull();
double ans=0;
for (int i=1;i<=m;i++) ans+=get_len(ch[i]-ch[i+1]);
ans+=pi*r*2.0;
printf("%.2lf\n",ans);
}