首页 > ACM题库 > HDU-杭电 > HDU 3372-Build Fences-计算几何-[解题报告]HOJ
2014
03-16

HDU 3372-Build Fences-计算几何-[解题报告]HOJ

Build Fences

问题描述 :

Winter is coming , chicks are preparing building fences to protect from cold wind.
They are going to use the limited fences to surround some trees , they will either make some trees out of the fences or leave them inside[the first image, OK].
Connect the Cities

They won’t make the fences touch trees outside and the fences should always be tighten.[the second image, forbidden]
Connect the Cities

(touch: two things have one or more points in common.)
Also , they want their living space as large as possible ,only the light blue districts are their living space.
The trees’ coordinates and their radius are given. No trees will touch each other.
You can use a fence whose length is L , what’s the largest area the chicks can live?

输入:

T(<=20) in the first line indicating case number.
For each case, n(1<=n<=16) , d(0<d<=1000) , L(0<=L<=1000000).
d : diameter of the trees , float number.
L : length of the fence , float number.
The next n lines each has two float numbers, x(|x|<=1000) , y(|y|<=1000) , which are the coodinates of the trees’ center.

输出:

T(<=20) in the first line indicating case number.
For each case, n(1<=n<=16) , d(0<d<=1000) , L(0<=L<=1000000).
d : diameter of the trees , float number.
L : length of the fence , float number.
The next n lines each has two float numbers, x(|x|<=1000) , y(|y|<=1000) , which are the coodinates of the trees’ center.

样例输入:

2

1 1 1
1 1

4 1 30
1 1
4 4
1 4
4 1

样例输出:

0.000
12.644

http://acm.hdu.edu.cn/showproblem.php?pid=3372

写的很乱 改了又改 最后重写的过程中 发现错在哪里了
l1=(a-b).len();
12=(a-o).len();
l3=(b-o).len();
应该是 l2=(a-inter).len(),l3=(b-inter).len(); 害死爹了
本来想重新写一偏工整的 但是实在是写不下去了
题意 给一堆圆形 在限定的长度(L)内将其圈起来 问可以圈的最大面积 最后要去掉圆形的面积
因为n==16 所以我直接 位运算枚举每种情况
有一个要注意的地方是 有写圆虽然没被选中 但是最后被包围在凸包里面了 也要算进去
至于长读和面积的求法:len=圆心的凸包围起来的长度+圆的周长,s=凸包的面积+len*r-(n-1)*carea (其中
n为凸包所包含的圆的个数,包括未被选中的,carea为圆的面积)
1 为被选中的圆在不在凸包内 直接用圆心去判断在不在点的凸包内就可以了
2 判断 凸包符不符合要求 判断未选中的且不在凸包内的点 和凸包边的距离会不会<周长

#include<stdio.h>
#include<string.h>
#include<cmath>
#include<vector>
#include<algorithm>
#define eps 1e-8
#define inf 1e100
#define N 20
#define pi acos(-1.0)
using namespace std;
int Sig(double a)
{
    return a<-eps?-1:a>eps;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double x0,double y0):x(x0),y(y0){}
    void in()
    {
        scanf("%lf%lf",&x,&y);
    }
    void out()
    {
        printf("%.3f %.3f\n",x,y);
    }
    Point operator * (double t)
    {
        return Point(t*x,t*y);
    }
    double len()
    {
        return sqrt(x*x+y*y);
    }
    double operator *(Point pt)
    {
        return x*pt.y-y*pt.x;
    }
    double operator ^(Point pt)
    {
        return pt.x*x+pt.y*y;
    }
    Point operator -(Point pt)
    {
        return Point(x-pt.x,y-pt.y);
    }
    Point operator +(Point pt)
    {
        return Point(x+pt.x,y+pt.y);
    }
};
double Dis(Point a,Point b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Xmult(Point o,Point a,Point b)
{
    return (a-o)*(b-o);
}
Point Intersection(Point u1,Point u2,Point v1,Point v2)//ÇóÁœÖ±ÏߵĜ»µã
{
    Point ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/
             ((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}
int con[100];
int cn;
Point po;
int cmp(Point a,Point b)
{
    double d=Xmult(po,a,b);
    if(d>0)
        return 1;
    if(d==0 && Dis(a,po)<Dis(b,po))
        return 1;
    return 0;
}
int Graham(Point p[],int n)
{
    int i,ind=0;
    for(i=1;i<n;i++)
        if(p[ind].y>p[i].y || (p[ind].y==p[i].y && p[ind].x>p[i].x))
            ind=i;
    swap(p[ind],p[0]);
    po=p[0];
    sort(p+1,p+n,cmp);
    con[0]=0;
    con[1]=1;
    cn=1;
    for(i=2;i<n;i++)
    {
        while(cn>0 && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0)
            cn--;
        con[++cn]=i;
    }

    int tmp=cn;
    for(i=n-2;i>=0;i--)
    {
        while(cn>tmp && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0)
            cn--;
        con[++cn]=i;//p[cn]==p[0];
    }
    Point tp[N];
    for(int i=0;i<cn;i++)
        tp[i]=p[con[i]];
    for(int i=0;i<cn;i++)
        p[i]=tp[i];
    n=cn;
    return cn;
}
int w[20];
void Init()
{
    for(int i=0;i<20;i++)
        w[i]=1<<i;
}
double Len(Point p[],int n,double d)
{
    double s=0;
    for(int i=0;i<n;i++)
        s+=(p[i]-p[(i+1)%n]).len();
    return s+d*pi;
}
double Area(Point p[],int n,double d)
{
    double s=0;
    for(int i=0;i<n;i++)
        s+=p[i]*p[(i+1)%n];
    s=fabs(s)*0.5;
    for(int i=0;i<n;i++)
        s+=d*0.5*(p[(i+1)%n]-p[i]).len();
    return s;
}
bool Point_line(Point o,Point a,Point b,double d)
{
    Point tmp=Point(b.y-a.y+o.x,a.x-b.x+o.y);
    Point inter=Intersection(o,tmp,a,b);
    double l1,l2,l3;
    l1=(a-b).len();
    l2=(a-o).len();
    l3=(b-o).len();
    double tt;
    if(!Sig(l1-l2-l3))
        tt= Dis(inter,o);
    else
        tt= min(Dis(o,a),Dis(o,b));
    return Sig(tt-d)<=0;
}
bool Point_line(Point a,Point p[],int n,double d)
{
    for(int i=0;i<n;i++)
    {
        if(Point_line(a,p[i],p[(i+1)%n],d))
            return 1;
    }
    return 0;
}
bool In_polygon(Point a,Point p[],int n)//判断点是不是在凸包内
{
    for(int i=0;i<n;i++)
        if(Sig(Xmult(p[i],p[(i+1)%n],a))<0)//在凸包的边上也不行!!!!!
            return 0;
    return 1;
}
bool Judge(Point p[],int n,bool hash[],int tn,Point tp[],double d)
{
    for(int i=0;i<tn;i++)
    {
        if(hash[i])
            continue;
        if(!In_polygon(tp[i],p,n) && Point_line(tp[i],p,n,d) )
            return 0;
    }
    return 1;
}
int main()
{
    int n,tn;
    double d,l;
    Point tp[N];
    Point p[N];
    bool hash[N];
    int t;
    Init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%lf%lf",&tn,&d,&l);
        for(int i=0;i<tn;i++)
            tp[i].in();
        double ans=0;
        int all=w[tn];
        for(int i=1;i<all;i++)
        {
            n=0;
            memset(hash,0,sizeof(hash));
            for(int j=0;j<tn;j++)
            {
                if(i&w[j])
                {
                    hash[j]=1;
                    p[n++]=tp[j];
                }
            }
            int nn=n;
            if(n==1)
                continue;
            if(n>2)
                n=Graham(p,n);
            if(Sig( Len(p,n,d)-l)>0)
                continue;
            if(n==2)//n==2 里面不能在放不被选中的圆
            {
                int flag=1;
                for(int j=0;j<tn;j++)
                    if(!hash[j] && Point_line(tp[j],p,n,d))
                    {
                        flag=0;
                        break;
                    }
                if(flag)
                    ans=max(ans,Area(p,n,d)-(nn-1)*pi*d*d/4);
            }
            else
            {
                if(Judge(p,n,hash,tn,tp,d))//判断凸包是否符合要求
                {

                    double area=Area(p,n,d);
                    for(int j=0;j<tn;j++)//判断有没有在凸包内的 没有被选中的圆
                    {
                        if(!hash[j] && In_polygon(tp[j],p,n))//适用n>=3
                                nn++;
                    }
                    ans=max(ans,area-(nn-1)*pi*d*d/4);
                }
            }
        }
        printf("%.3f\n",ans);
    }
    return 0;
}

  1. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  2. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  3. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  4. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  5. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  6. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  7. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  8. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  9. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  10. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  11. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  12. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  13. 让我们好好想想:城管就必定是坏人,小贩就必定是无辜者?难道我们聘城管的第一条就是必须爱打仗,小贩的人生原则第一条就是建设和谐城市?!城管和小贩都是这个社会的一员,都和我们一样有着人性中的恶与善。一个是执法阶层的最底人员,一个是社会阶层的最底人员,退无可退

  14. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧