洛谷P3829 [SHOI2012]信用卡凸包(凸包)
思路:
模拟一下题意给出的图就会发现:答案等于圆心的长方形周长之和+圆的周长。
简略证明就是圆心角相加正好为360°
扩展到一般情况:
答案为圆心构成的凸包周长+圆的周长。
所以问题就转化成了两个子问题:
1.如果根据给出的中心和角度求四个圆心的坐标
2.如何求凸包
对于问题2我们可以愉快的上凸包的模板了!
对于问题1:
设当前点为(x,y),将其绕原点逆时针旋转z °得到的坐标为:(x∗cos(z)−y∗sin(z),y∗cos(z)+x∗sin(z))
旋转完后再给该点加上基准点就可以了,该题的基准点为信用卡的中心。
最后,有几个小的注意点:
1.凸包的模板里的下标是从0开始,输出的答案也是从0开始的;
2.不要忘记计算凸包的终点到起点的距离。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+100; const double PI = acos(-1); const double eps=1e-8; int sgn(double x){///判断x是否等于0 if(fabs(x)<eps) return 0; if(x<0) return -1; else return 1; } struct point{ double x,y; point(){} point(double x,double y):x(x),y(y){} point operator+(point b){ return point(x+b.x,y+b.y); } point operator-(point b){ return point(x-b.x,y-b.y); } bool operator == (point b){ return sgn(x-b.x)==0&&sgn(y-b.y)==0; } bool operator<(point b)const{ if(sgn(x-b.x)==0) return sgn(y-b.y)<0; return sgn(x-b.x)<0; } }; point s[maxn],g[maxn],h[maxn]; int n; double dot(point a,point b){return a.x*b.x+a.y*b.y;} double cross(point a,point b){return a.x*b.y-a.y*b.x;} double cul(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } struct line{ point p1,p2; line(){} line(point p1,point p2):p1(p1),p2(p2){} }; double mult(point a,point b,point o){ ///计算叉乘ao和bo return (a.x-o.x)*(b.y-o.y)>=(b.x-o.x)*(a.y-o.y); } int Graham(int n){ int idx=1; sort(s,s+n); if(!n) return 0; h[0]=s[0]; if(n==1) return 0; h[1]=s[1]; if(n==2) return 0; h[2]=s[2]; ///求凸包的上半部分 for(int i=2;i<n;i++){ while(idx&&(mult(s[i],h[idx],h[idx-1]))) idx--; h[++idx]=s[i]; } int tmp=idx; h[++idx]=s[n-2]; for(int i=n-3;i>=0;i--){ while(idx!=tmp&&(mult(s[i],h[idx],h[idx-1]))) idx--; h[++idx]=s[i]; } return idx; } //说明 返回值为凸包点的个数,h数组存储的是凸包中的点。 point rotate(point a,double t){ ///旋转 double c=cos(t),s=sin(t); return point{a.x*c-a.y*s,a.x*s+a.y*c}; } int main(){ int m;cin>>m; double a,b,r; cin>>b>>a>>r; a/=2.0;b/=2.0; for(int i=1;i<=m;i++){ double x,y,z;cin>>x>>y>>z; point t={x,y}; s[n++]=rotate({a-r,b-r},z)+t; s[n++]=rotate({r-a,b-r},z)+t; s[n++]=rotate({r-a,r-b},z)+t; s[n++]=rotate({a-r,r-b},z)+t; } int res=Graham(n); double ans=2*PI*r; for(int i=0;i<res-1;i++) ans=ans+cul(h[i],h[i+1]); ans+=(cul(h[res-1],h[0])); printf("%.2f\n",ans); return 0; }