bzoj 2829 信用卡凸包（凸包）

2829: 信用卡凸包

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1342 Solved: 577
[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

3.333

HINT

本样例中的2张信用卡的轮廓在上图中用实线标出，如果视1.5707963268为Pi/2(pi为圆周率),则其凸包的周长为16+4*sqrt(2)

【思路】

凸包

将一张信用卡看作以四个圆心为顶点的矩形，求出凸包周长后再加一个圆周长。

【代码】

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
 7 using namespace std;
 8 
 9 const int N = 400000+10; 
10 const double PI = acos(-1.0);
11 const double eps = 1e-12;
12 
13 int dcmp(double x) {
14     if(fabs(x)<eps) return 0; else return x<0? -1:1;
15 }
16 
17 struct Pt {
18     double x,y;
19     Pt(double x=0,double y=0) :x(x),y(y) {};
20 };
21 typedef Pt vec;
22 
23 vec operator - (Pt a,Pt b) { return vec(a.x-b.x,a.y-b.y); }
24 vec operator + (vec a,vec b) { return vec(a.x+b.x,a.y+b.y); }
25 bool operator == (Pt a,Pt b) { 
26     return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
27 }
28 bool operator < (const Pt& a,const Pt& b) {
29     return a.x<b.x || (a.x==b.x && a.y<b.y);
30 }
31 
32 vec rotate(vec a,double x) {
33     return vec(a.x*cos(x)-a.y*sin(x),a.x*sin(x)+a.y*cos(x));
34 }
35 double cross(vec a,vec b) { return a.x*b.y-a.y*b.x; }
36 double dist(Pt a,Pt b) {
37     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
38 }
39 
40 vector<Pt> ConvexHull(vector<Pt> p) {
41     sort(p.begin(),p.end());
42     p.erase(unique(p.begin(),p.end()),p.end());
43     int n=p.size() , m=0;
44     vector<Pt> ch(n+1);
45     for(int i=0;i<n;i++) {
46         while(m>1 && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
47         ch[m++]=p[i];
48     }
49     int k=m;
50     for(int i=n-2;i>=0;i--) {
51         while(m>k && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
52         ch[m++]=p[i];
53     }
54     if(n>1) m--;
55     ch.resize(m); return ch;
56 }
57 
58 int n;
59 double a,b,r;
60 vector <Pt> p,ch;
61 
62 int main() {
63     scanf("%d%lf%lf%lf",&n,&b,&a,&r);
64     a-=2*r , b-=2*r; a/=2 , b/=2;
65     double x,y,ang,ans=0;
66     FOR(i,1,n) {
67         scanf("%lf%lf%lf",&x,&y,&ang);
68         Pt o=Pt(x,y);
69         p.push_back(o+rotate(vec(-a,-b),ang));
70         p.push_back(o+rotate(vec(-a,b),ang));
71         p.push_back(o+rotate(vec(a,-b),ang));
72         p.push_back(o+rotate(vec(a,b),ang));
73     }
74     ch=ConvexHull(p);
75     n=ch.size();
76     FOR(i,0,n-2)
77         ans+=dist(ch[i],ch[i+1]);
78     ans+=dist(ch[n-1],ch[0]);
79     ans+=2*PI*r;
80     printf("%.2lf",ans);
81     return 0;
82 }

View Code