洛谷P3829 [SHOI2012]信用卡凸包(点的旋转+凸包)

简介: 洛谷P3829 [SHOI2012]信用卡凸包(点的旋转+凸包)

洛谷P3829 [SHOI2012]信用卡凸包(凸包)

原题链接

思路:

模拟一下题意给出的图就会发现:答案等于圆心的长方形周长之和+圆的周长。

简略证明就是圆心角相加正好为360°

扩展到一般情况:

答案为圆心构成的凸包周长+圆的周长。

所以问题就转化成了两个子问题:

1.如果根据给出的中心和角度求四个圆心的坐标

2.如何求凸包

对于问题2我们可以愉快的上凸包的模板了!

对于问题1:

设当前点为(x,y),将其绕原点逆时针旋转z °得到的坐标为:xcos(z)ysin(z),ycos(z)+xsin(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;
}
目录
相关文章
|
算法
算法提高:计算几何基础 | 详解凸包问题
点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上,或者在其内
151 0
算法提高:计算几何基础 | 详解凸包问题
|
算法
秒懂算法 | 计算几何:圆
计算几何的基础是点积和叉积,它们定义了向量的大小和方向的关系,是其他计算几何概念和算法的出发点。在点积和叉积的基础上,本篇重点介绍圆覆盖。 计算几何题目的代码大多繁琐冗长,因此掌握模板代码是学习计算几何的关键。本篇精心组织了经典的几何模板
18088 1
秒懂算法 | 计算几何:圆
|
机器学习/深度学习
Leecode 892. 三维形体的表面积
Leecode 892. 三维形体的表面积
55 0
Leecode 695. 岛屿的最大面积
Leecode 695. 岛屿的最大面积
33 0
洛谷P3194 [HNOI2008]水平可见直线(计算几何+单调栈)
洛谷P3194 [HNOI2008]水平可见直线(计算几何+单调栈)
99 0
洛谷P3194 [HNOI2008]水平可见直线(计算几何+单调栈)
|
Python
LeetCode每日一题——883. 三维形体投影面积
在 n x n 的网格 grid 中,我们放置了一些与 x,y,z 三轴对齐的 1 x 1 x 1 立方体。
117 0
LeetCode每日一题——883. 三维形体投影面积
|
机器学习/深度学习
1036. 逃离大迷宫 : BFS + 给定障碍物所能围成的最大面积
1036. 逃离大迷宫 : BFS + 给定障碍物所能围成的最大面积
|
算法 Windows 小程序