这题居然是WF的题， 应属于签到题。。
求一个多边形是否能被一个宽为d的矩形框住。
可以求一下凸包，然后枚举每条凸包的边，找出距离最远的点。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100000
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
const int MAXN=;
struct point
{
double x,y;
point(double x=,double y=):x(x),y(y){}
}p[N],ch[N];
typedef point pointt;
point operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
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 cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
double mul(point p0,point p1,point p2)
{
return cross(p1-p0,p2-p0);
}
double dis(point a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
bool cmp(point a,point b)
{
if(dcmp(mul(p[],a,b))==)
return dis(a-p[])<dis(b-p[]);
else
return dcmp(mul(p[],a,b))>;
}
int Graham(int n)
{
int i,k = ,top;
point tmp;
for(i = ; i < n; i++)
{
if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x))
k = i;
}
if(k!=)
{
tmp = p[];
p[] = p[k];
p[k] = tmp;
}
sort(p+,p+n,cmp);
ch[] = p[];
ch[] = p[];
top = ;
for(i = ; i < n ; i++)
{
while(top>&&dcmp(mul(ch[top-],ch[top],p[i]))<)
top--;
top++;
ch[top] = p[i];
}
return top;
}
double distancetoline(point p,point a,point b)
{
point v1 = b-a,v2 = p-a;
return fabs(cross(v1,v2))/dis(v1);
}
int main()
{
int i,j;
int n,kk=;
while(scanf("%d",&n)&&n)
{
for(i = ; i < n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
int m = Graham(n);
ch[m+] = ch[];
double ans = INF;
for(i = ; i <= m; i++)
{
double ts = ;
for(j = ; j <= m ; j++)
ts = max(ts,distancetoline(ch[j],ch[i],ch[i+]));
ans = min(ans,ts);
}
ans = ceil(ans*)/;
printf("Case %d: %.2lf\n",++kk,ans);
}
return ;
}