UVA-10652 (凸包)

时间：2023-03-09 19:49:10
UVA-10652 (凸包)

题意：

给n个矩形,问包含这些矩形的尽量小的凸多边形的面积是多少;

思路：

由于给的矩形的形式是给出了中心的坐标,长和宽以及旋转的角度,所以先转换成四个点的坐标,然后求一遍凸包就好了,第一次写凸包,代码都是白书上的;

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bits/stdc++.h>

#include <stack>

#include <map>

using namespace std;

#define For(i,j,n) for(int i=j;i<=n;i++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef  long long LL;

template<class T> void read(T&num) {

    char CH; bool F=false;

    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());

    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());

    F && (num=-num);

}

int stk[70], tp;

template<class T> inline void print(T p) {

    if(!p) { puts("0"); return; }

    while(p) stk[++ tp] = p%10, p/=10;

    while(tp) putchar(stk[tp--] + '0');

    putchar('\n');

}

const LL mod=1e9+7;

const double PI=acos(-1.0);

const int inf=1e9;

const int N=1e5+20;

const int maxn=1e6+4;

const double eps=1e-12;

struct Point

{

    double x,y;

    Point (double x=0,double y=0):x(x),y(y) {}

};

typedef Point Vector;

Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}

Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}

Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}

bool operator < (const Point& a,const Point& b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}

Vector Rotate(Vector A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}

int dcmp(double x){if(fabs(x)<eps) return 0;else return x<0 ? -1:1;}

bool operator == (const Point& a,const Point& b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}

double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}

double Length(Vector A){return sqrt(Dot(A,A));}

double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}

double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

int ConvexHull(Point *p,int n,Point *ch)

{

    sort(p,p+n);

    int m=0;

    for(int i=0;i<n;i++)

    {

        while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;

        ch[m++]=p[i];

    }

    int k=m;

    for(int i=n-2;i>=0;i--)

    {

        while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;

        ch[m++]=p[i];

    }

    if(n>1)m--;

    return m;

}

double Area(Point *p,int n)

{

    double area=0;

    for(int i=1;i<n-1;i++)area+=Cross(p[i]-p[0],p[i+1]-p[0]);

    return area/2;

}

int main()

{

    Point P[2410],ch[2410];

    int t;

    read(t);

    while(t--)

    {

        int n,cnt=0;

        double sum=0;

        read(n);

        double x,y,w,h,j,ang;

        For(i,1,n)

        {

            scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&j);

            sum+=w*h;

            Point o(x,y);

            ang=-j*PI/180;

            P[cnt++]=o+Rotate(Vector(-w/2,-h/2),ang);

            P[cnt++]=o+Rotate(Vector(-w/2,h/2),ang);

            P[cnt++]=o+Rotate(Vector(w/2,-h/2),ang);

            P[cnt++]=o+Rotate(Vector(w/2,h/2),ang);

        }

        int m=ConvexHull(P,cnt,ch);

        double ans=100*sum/Area(ch,m);

        printf("%.1lf %%\n",ans);

    }

    return 0;

}

　　

相关文章