BZOJ 2829 凸包

思路:

把信用卡周围去掉  只剩下中间的长方形

最后的答案加上一个圆

//By SiriusRen
#include <bits/stdc++.h>
using namespace std;
const int N=;
const double eps=1e-;
int card,n,m,k;
double a,b,r,xx,yy,theta,Ans;
struct Point{
double x,y;Point(){}
Point(double X,double Y){x=X,y=Y;}
}point[N],tubao[N];
bool cmp1(Point a,Point b){if(abs(a.x-b.x)>eps)return a.x<b.x;return a.y<b.y;}
double cross(Point a,Point b,Point c){
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
double dis(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
scanf("%d%lf%lf%lf",&card,&a,&b,&r);
Ans+=*acos(-)*r;
a=a-*r,b=b-*r;
for(int i=;i<=card;i++){
scanf("%lf%lf%lf",&xx,&yy,&theta);
point[++n]=Point(xx-sin(theta)*a/-cos(theta)*b/,yy+cos(theta)*a/-sin(theta)*b/);
point[++n]=Point(xx-sin(theta)*a/+cos(theta)*b/,yy+cos(theta)*a/+sin(theta)*b/);
point[++n]=Point(xx+sin(theta)*a/-cos(theta)*b/,yy-cos(theta)*a/-sin(theta)*b/);
point[++n]=Point(xx+sin(theta)*a/+cos(theta)*b/,yy-cos(theta)*a/+sin(theta)*b/);
}
sort(point+,point++n,cmp1);
for(int i=;i<=n;i++){
while(m>&&cross(tubao[m],point[i],tubao[m-])<eps)m--;
tubao[++m]=point[i];
}k=m;
for(int i=n-;i;i--){
while(m>k&&cross(tubao[m],point[i],tubao[m-])<eps)m--;
tubao[++m]=point[i];
}
for(int i=;i<m;i++)Ans+=dis(tubao[i],tubao[i+]);
printf("%.2lf\n",Ans);
}
上一篇:SQL内外连接的区别


下一篇:UVA 11248 - Frequency Hopping(网络流量)