设为首页收藏本站

中国膜结构网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

膜结构车棚
膜结构车棚膜结构资质国产膜材 膜结构网中国膜结构协会
查看: 445|回复: 0

多边形最小外接矩形 旋转卡壳

[复制链接]
  • TA的每日心情
    开心
    2021-6-19 14:40
  • 签到天数: 1539 天

    [LV.Master]伴坛终老

    发表于 2020-11-24 22:30 | 显示全部楼层 |阅读模式
    多边形最小外接矩形 旋转卡壳
    1. 代码:

    2. #include<stdio.h>
    3. #include<math.h>
    4. #include<string.h>
    5. #include<stdlib.h>
    6. #include<iostream>
    7. #include<algorithm>
    8. #include<time.h>
    9. using namespace std;
    10. const int maxn=4000+9;
    11. const double eps=1e-7;
    12. struct point{
    13.     double x,y;
    14.     point(double x=0,double y=0):x(x),y(y){}
    15. };
    16. typedef point P;
    17. typedef point Point;
    18. typedef point Vector;
    19. Vector operator + (Vector a, Vector b){//向量加法
    20.     return Vector(a.x + b.x, a.y + b.y);
    21. }
    22. Vector operator - (Vector a, Vector b){//向量减法
    23.     return Vector(a.x - b.x, a.y - b.y);
    24. }
    25. Vector operator * (Vector a, double p){//向量数乘
    26.     return Vector(a.x*p, a.y*p);
    27. }
    28. Vector operator / (Vector a, double p){//向量数除
    29.     return Vector(a.x / p, a.y / p);
    30. }
    31. int dcmp(double x){//精度三态函数(>0,<0,=0)
    32.     if (fabs(x) < eps)return 0;
    33.     else if (x > 0)return 1;
    34.     return -1;
    35. }
    36. bool operator == (const Point &a, const Point &b){//向量相等
    37.     return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
    38. }
    39. double Cross(P a,P b){ // 叉积 平行四边形面积
    40.     return (a.x*b.y)-(b.x*a.y);
    41. }
    42. double Cross(P a,P b,P c){ // 叉积 ab_ac
    43.     return Cross(c-a,b-a);
    44. }
    45. double Dot(P a,P b){
    46.     return a.x*b.x+a.y*b.y;
    47. }
    48. double Dot(P a,P b,P c){
    49.     return Dot(b-a,c-a);
    50. }
    51. double LengthPow(Vector v){
    52.     return v.x*v.x+v.y*v.y;
    53. }
    54. double Distance(P a,P b){
    55.     return sqrt(LengthPow(a-b));
    56. }

    57. point p[maxn],ans[maxn];
    58. int n,top;
    59. point Tmp;//选好的起点
    60. bool cmp(point a,point b){
    61.     double ans=Cross(a-Tmp,b-Tmp);
    62.     if(dcmp(ans)==0)return dcmp(Distance(a,Tmp)-Distance(b,Tmp))<0;
    63.     return ans>0;//表示a到b是逆时针转
    64. }
    65. // 去掉共线点
    66. void Graham(point p[],int n,point ans[],int &top){
    67.     if(n<3){
    68.         for(int i=1;i<=n;i++)ans[i]=p[i];
    69.         top=n;
    70.         return;
    71.     }
    72.     for(int i=2;i<=n;i++){
    73.         if(p[i].y<p[1].y||(dcmp(p[i].y-p[1].y)==0&&p[i].x<p[1].x))
    74.             swap(p[1],p[i]);
    75.     }
    76.     Tmp=p[1];
    77.     sort(p+2,p+1+n,cmp);
    78.     ans[1]=p[1],ans[2]=p[2],top=2;
    79.     for(int i=3;i<=n;i++){
    80.         while(top>2&&dcmp(Cross(ans[top]-ans[top-1],p[i]-ans[top]))<=0)top--;
    81.         ans[++top]=p[i];
    82.         if(top>2&&dcmp(Cross(ans[top]-ans[top-1],ans[top-1]-ans[top-2]))==0)ans[top-1]=ans[top],--top;
    83.     }
    84. }

    85. #define rep(i,a,b) for(int i=a;i<=b;i++)

    86. double RotateCalipers(P *p,int n){
    87.     int r=2,l=2,up=2;
    88.     double area=1e18;
    89.     p[n+1]=p[1];
    90.     rep(i,1,n){
    91.         while(dcmp(Cross(p[i],p[i+1],p[up+1])-
    92.             Cross(p[i],p[i+1],p[up])<=0))up=up%n+1;
    93.         while(dcmp(Dot(p[i],p[i+1],p[r+1])-
    94.             Dot(p[i],p[i+1],p[r])>0))r=r%n+1;
    95.         if(i==1)l=r;
    96.         while(dcmp(Dot(p[i],p[i+1],p[l+1])-
    97.             Dot(p[i],p[i+1],p[l])<=0))l=l%n+1;
    98.         double d=Distance(p[i],p[i+1])*Distance(p[i],p[i+1]);
    99.         area=min(area, fabs(Cross(p[i],p[i+1],p[up]))*
    100.             fabs(Dot(p[i],p[i+1],p[r])-Dot(p[i],p[i+1],p[l]))/d );
    101.     }
    102.     return area;
    103. }

    104. int main(){
    105.     int t,cas=0;scanf("%d",&t);
    106.     while(t--){
    107.         printf("Case #%d:\n",++cas);
    108.         int n;scanf("%d",&n);n<<=2;
    109.         rep(i,1,n){
    110.             scanf("%lf%lf",&p[i].x,&p[i].y);
    111.         }
    112.         Graham(p,n,ans,top);
    113.         printf("%.0f\n",RotateCalipers(ans,top));
    114.     }
    115. }
    复制代码
    回复


    http://www.mjgw.org/ 专业从事膜结构设计、制作加工、施工安装的膜结构工程服务,能够为客户提供专业的膜结构整体解决方案。做中国最好的膜结构综合服务平台。欢迎大家联系电话:198-7840-1958,QQ:463017170.
    相关关键词:膜结构车棚,膜结构车棚覆盖,膜结构车棚公司,膜结构车棚多少钱,膜结构车棚厂家,膜结构车棚价格,社区膜结构车棚,膜结构车棚膜布厂家 ,膜结构车棚哪家好,膜结构车棚多少钱一米,膜结构车棚报价,膜结构车棚哪里有,膜结构车棚定制,膜结构车棚安装,膜结构车棚设计,膜结构车棚电话,膜结构车棚加工,膜结构车棚膜布价格,膜结构车棚批发,膜结构车棚制造商,膜结构车棚生产厂家,膜结构车棚设计,膜结构车棚施工,膜结构车棚多少钱一平米,膜结构车棚订制,张拉膜车棚,张拉膜车棚覆盖,张拉膜车棚公司,张拉膜车棚多少钱,张拉膜车棚厂家,张拉膜车棚价格,社区张拉膜车棚,张拉膜车棚膜布厂家 ,张拉膜车棚哪家好,张拉膜车棚多少钱一米,张拉膜车棚报价,张拉膜车棚哪里有,张拉膜车棚定制,张拉膜车棚安装,张拉膜车棚设计,张拉膜车棚电话,张拉膜车棚加工,张拉膜车棚膜布价格,张拉膜车棚批发,张拉膜车棚制造商,张拉膜车棚生产厂家,张拉膜车棚设计,张拉膜车棚施工,张拉膜车棚多少钱一平米,张拉膜车棚订制,常用膜材品牌:德国杜肯、法国法拉利、德国海德斯、德国米乐、日本平岗、韩国秀博、比利时希运、美国赫虏伯、中国科宝、上海慧遥。

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    关闭

    推荐膜材品牌上一条 /6 下一条

    进口膜材 国产膜材 pvdf膜材ptfe膜材ETFE膜材
    最好的膜结构公司 一级膜结构资质 膜结构一级资质
    膜结构设计-膜结构十大品牌-etfe设计-充气膜结构
    诺科膜结构
    遨都膜结构设计
    中国膜结构网
    中国空间膜结构

    QQ|申请友链|手机版|中国膜结构论坛