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)

【思路】

凸包

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

【代码】

 #include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int N = +;
const double PI = acos(-1.0);
const double eps = 1e-; int dcmp(double x) {
if(fabs(x)<eps) return ; else return x<? -:;
} struct Pt {
double x,y;
Pt(double x=,double y=) :x(x),y(y) {};
};
typedef Pt vec; vec operator - (Pt a,Pt b) { return vec(a.x-b.x,a.y-b.y); }
vec operator + (vec a,vec b) { return vec(a.x+b.x,a.y+b.y); }
bool operator == (Pt a,Pt b) {
return dcmp(a.x-b.x)== && dcmp(a.y-b.y)==;
}
bool operator < (const Pt& a,const Pt& b) {
return a.x<b.x || (a.x==b.x && a.y<b.y);
} vec rotate(vec a,double x) {
return vec(a.x*cos(x)-a.y*sin(x),a.x*sin(x)+a.y*cos(x));
}
double cross(vec a,vec b) { return a.x*b.y-a.y*b.x; }
double dist(Pt a,Pt b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} vector<Pt> ConvexHull(vector<Pt> p) {
sort(p.begin(),p.end());
p.erase(unique(p.begin(),p.end()),p.end());
int n=p.size() , m=;
vector<Pt> ch(n+);
for(int i=;i<n;i++) {
while(m> && cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-;i>=;i--) {
while(m>k && cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
if(n>) m--;
ch.resize(m); return ch;
} int n;
double a,b,r;
vector <Pt> p,ch; int main() {
scanf("%d%lf%lf%lf",&n,&b,&a,&r);
a-=*r , b-=*r; a/= , b/=;
double x,y,ang,ans=;
FOR(i,,n) {
scanf("%lf%lf%lf",&x,&y,&ang);
Pt o=Pt(x,y);
p.push_back(o+rotate(vec(-a,-b),ang));
p.push_back(o+rotate(vec(-a,b),ang));
p.push_back(o+rotate(vec(a,-b),ang));
p.push_back(o+rotate(vec(a,b),ang));
}
ch=ConvexHull(p);
n=ch.size();
FOR(i,,n-)
ans+=dist(ch[i],ch[i+]);
ans+=dist(ch[n-],ch[]);
ans+=*PI*r;
printf("%.2lf",ans);
return ;
}

最新文章

  1. 学用了QT觉得QT较怪异
  2. linux SVNUP显示无法连接主机
  3. 在浏览器中将表格导入到本地的EXCEL文件,注意控制内存
  4. HS光流算法详解&lt;转载&gt;
  5. JQ 模仿注册时等待的时间
  6. vmware虚拟机迁移导致的eth0消失问题
  7. file_get_contents post数据
  8. Cordova环境搭建与hello word
  9. Ch2. Loop Structure
  10. maven快速上手
  11. Linux ext2文件系统之初步思考
  12. 基于PDO的简易ORM
  13. Access Token 与 Refresh Token【转载哒科普啊】
  14. Spring Boot 异常处理
  15. Java ee第七周作业
  16. .w调用action
  17. springboot打包部署到tomcat
  18. Codeforces Round #368 (Div. 2) B. Bakery 水题
  19. NSLineBreakMode 的区别
  20. 通过经纬度坐标计算距离的方法(经纬度距离计算)ZZ

热门文章

  1. SQL的经典操作——批量复制同行的其它列数据到其它列数据
  2. 九度OJ 1077 最大序列和 -- 动态规划
  3. Hibernate的检索策略
  4. sass中常用mixin
  5. yii2源码学习笔记(十九)
  6. C++顺序容器类总结
  7. IT全称
  8. C#网页自动登录和提交POST信息的多种方法(转)
  9. The CircuitCalculator.com Blog a blog with live web calculators Home About Policies Contact PCB
  10. Pentaho Data Integration (二) Spoon