「BZOJ2829」信用卡凸包
Description
.jpg)
Input
.jpg)
Output
.jpg)
Sample Input
2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268
Sample Output
21.66
HINT
.jpg)
本样例中的2张信用卡的轮廓在上图中用实线标出，如果视1.5707963268为
Pi/2(pi为圆周率),则其凸包的周长为16+4*sqrt(2)
题解
把圆形拿出来求凸包周长，最后加上一个圆的周长
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define rad 100000000 #define inf 1000000000 #define ll long long #define eps 1e-8 #define pa pair<ll,int> #define pi acos(-1) using namespace std; double ans; int n,cnt,top; double a,b,r; double sqr(double x) { return x*x; } struct P{ double x,y; P(double _x=0,double _y=0){x=_x;y=_y;} friend P operator-(P a,P b){ return P(a.x-b.x,a.y-b.y); } friend double operator*(P a,P b){ return a.x*b.y-a.y*b.x; } friend bool operator<(P a,P b){ if(fabs(a.y-b.y)<eps)return a.x<b.x; return a.y<b.y; } friend double dis2(P a){ return sqr(a.x)+sqr(a.y); } }p[400005],q[400005]; struct rec{ double x,y,angle; }o[100005]; void print(P a) { printf("%.2lf %.2lf\n",a.x,a.y); } P move(P a,double d,double A) { return P(a.x+d*cos(A),a.y+d*sin(A)); } bool cmp(P a,P b) { if(fabs((a-p[1])*(b-p[1]))<eps)return dis2(p[1]-a)<dis2(p[1]-b); return (a-p[1])*(b-p[1])>0; } void graham() { for(int i=1;i<=cnt;i++) if(p[i]<p[1])swap(p[i],p[1]); sort(p+2,p+cnt+1,cmp); for(int i=1;i<=cnt;i++) { while(top>1&&(q[top]-q[top-1])*(p[i]-q[top-1])<-eps) top--; q[++top]=p[i]; } } void build() { for(int i=1;i<=n;i++) for(int k=0;k<4;k++) { P t=move(P(o[i].x,o[i].y),b/2,o[i].angle+k*pi/2); p[++cnt]=move(t,a/2,o[i].angle+(k+1)*pi/2); swap(a,b); } } void solve() { q[top+1]=q[1]; for(int i=1;i<=top;i++) ans+=sqrt(dis2(q[i]-q[i+1])); } int main() { scanf("%d",&n); scanf("%lf%lf%lf",&a,&b,&r);a-=2*r;b-=2*r; ans+=2*pi*r; for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&o[i].x,&o[i].y,&o[i].angle); build(); graham(); solve(); printf("%.2lf",ans); return 0; } |
计数器 9787129
OI 课件=>
OI 课件=>
请问如何证明是加上1个圆
目测巨大代码贴错了