2014
03-16

# 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].

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

(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();

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小值吧