bzoj 2829 信用卡凸包(凸包)
2024-10-15 14:21:11
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 ;
}
最新文章
- 学用了QT觉得QT较怪异
- linux SVNUP显示无法连接主机
- 在浏览器中将表格导入到本地的EXCEL文件,注意控制内存
- HS光流算法详解<;转载>;
- JQ 模仿注册时等待的时间
- vmware虚拟机迁移导致的eth0消失问题
- file_get_contents post数据
- Cordova环境搭建与hello word
- Ch2. Loop Structure
- maven快速上手
- Linux ext2文件系统之初步思考
- 基于PDO的简易ORM
- Access Token 与 Refresh Token【转载哒科普啊】
- Spring Boot 异常处理
- Java ee第七周作业
- .w调用action
- springboot打包部署到tomcat
- Codeforces Round #368 (Div. 2) B. Bakery 水题
- NSLineBreakMode 的区别
- 通过经纬度坐标计算距离的方法(经纬度距离计算)ZZ
热门文章
- SQL的经典操作——批量复制同行的其它列数据到其它列数据
- 九度OJ 1077 最大序列和 -- 动态规划
- Hibernate的检索策略
- sass中常用mixin
- yii2源码学习笔记(十九)
- C++顺序容器类总结
- IT全称
- C#网页自动登录和提交POST信息的多种方法(转)
- The CircuitCalculator.com Blog a blog with live web calculators Home About Policies Contact PCB
- Pentaho Data Integration (二) Spoon