题目描述：

给你两个凸多边形A和B，B的平移方向，问B至少移动多少，B的移动“轨迹”可以覆盖掉A面积的（1-k）倍（k是小数）

解题报告：

由于是移动轨迹的覆盖，所以覆盖面积一定与移动距离成正比，所以可以二分答案。

对于每一个答案，可以得到凸包B移动到的最后的凸包位置（即各个点移动到的位置），

那么轨迹构成的图形就是B初始的顶点和B移动后的顶点构成的凸包。

然后用半平面交的方法求轨迹的凸包和A凸包的面积交是多少。

大于等于覆盖要求，边界左移，否则右移，log的速度得到最优解。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 120
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point{double x,y;}side, a[MAXN], b[MAXN], base, c[MAXN * 4], d[MAXN * 4];
double xmult(point p1,point p2,point p0){
 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int same_side(point p1,point p2,point l1,point l2){
 return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}
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;
}
//将多边形沿l1,l2确定的直线切割在side侧切割,保证l1,l2,side不共线
void polygon_cut(int& n,point* p,point l1,point l2,point side){
 point pp[100];
 int m=0,i;
 for (i=0;i<n;i++){
  if (same_side(p[i],side,l1,l2))
   pp[m++]=p[i];
  if (!same_side(p[i],p[(i+1)%n],l1,l2)&&!(zero(xmult(p[i],l1,l2))&&zero(xmult(p[(i+1)%n],l1,l2))))
   pp[m++]=intersection(p[i],p[(i+1)%n],l1,l2);
 }
 for (n=i=0;i<m;i++)
  if (!i||!zero(pp[i].x-pp[i-1].x)||!zero(pp[i].y-pp[i-1].y))
   p[n++]=pp[i];
 if (zero(p[n-1].x-p[0].x)&&zero(p[n-1].y-p[0].y))
  n--;
 if (n<3)
  n=0;
}
int na, nb, cnt, sta[MAXN * 4], num, move[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
bool inside()
{
    double tmp = xmult(side, b[nb - 1], b[0]);
    if (zero(tmp)) return false;
    for(int i = 0; i < nb - 1; i++)
    {
        double jeo = xmult(side, b[i], b[i + 1]);
        if (zero(jeo) || tmp * jeo < 0) return false;
    }
    return true;
}
double ans, ang, k, A1, A2;
bool cmp(point a, point b){ return (a.y < b.y || a.y == b.y && a.x < b.x);}
bool CrossLeft(point p1, point p2, point p3)//是否严格左转，共线不算左转
{
    return ((p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y)) < 0;
}
void Jarvis()
{
    sort(c, c + cnt, cmp); int tail = 0; num = 0;
    sta[tail++] = 0, sta[tail++] = 1;
    for(int i = 2; i < cnt; i++)
    {
        while(tail > 1 && !CrossLeft(c[sta[tail - 2]], c[sta[tail - 1]], c[i]))
            tail--;
        sta[tail++] = i;
    }
    for(int i = 0; i < tail; i++) d[num++] = c[sta[i]];
    tail = 0; sta[tail++] = cnt - 1; sta[tail++] = cnt - 2;
    for(int i = cnt - 3; i >= 0; i--)
    {
        while(tail > 1 && !CrossLeft(c[sta[tail - 2]], c[sta[tail - 1]], c[i]))
            tail--;
        sta[tail++] = i;
    }
    for(int i = 0; i < tail; i++) d[num++] = c[sta[i]];
}
void jeogia()
{
    double l = 0, r = 20000;
    ans = 10000000;
    while(r - l >= 1e-8)
    {
        double mid = (l + r) * 0.5; cnt = 0;
        for(int i = 0; i < na; i++)
        {
            c[cnt++] = a[i];
            c[cnt].x = a[i].x + base.x * mid;
            c[cnt++].y = a[i].y + base.y * mid;
        }
        Jarvis();
        polygon_cut(num, d, b[nb - 1], b[0], side);
        for(int i = 0; i < nb - 1; i++)
            polygon_cut(num, d, b[i], b[i + 1], side);
        A2 = xmult(d[0], d[num - 1], d[0]);
        for(int i = 0; i < num - 1; i++)
            A2 += xmult(d[0], d[i], d[i + 1]);
        A2 = fabs(A2);
        if (A1 * (1 - k) - A2 >= 1e-7) l = mid;
        else
        {
            if (mid < ans) ans = mid;
            r = mid;
        }
    }
}
int main()
{
    while(scanf("%d", &nb) != EOF)
    {
        for(int i = 0; i < nb; i++) scanf("%lf%lf", &b[i].x, &b[i].y);
        scanf("%d", &na);
        for(int i = 0; i < na; i++) scanf("%lf%lf", &a[i].x, &a[i].y);
        A1 = xmult(b[0], b[nb - 1], b[0]);
        for(int i = 0; i < nb - 1; i++)
            A1 += xmult(b[0], b[i], b[i + 1]);
        A1 = fabs(A1);
        scanf("%lf%lf", &ang, &k);
        base.y = sin(ang * 3.141592653 / 180);
        base.x = cos(ang * 3.141592653 / 180);
        for(double xx = 0.5; xx <= 2; xx += 0.5)
            for(int i = 0; i < nb; i++)
                for(int j = 0; j < 8; j++)
                {
                    side = b[i]; side.x += move[j][0] * xx;
                    side.y += move[j][1] * xx; if (inside()) goto lable1;
                }
        lable1:jeogia();
        if (ans == 10000000) printf("-1\n");
        else printf("%.4f\n", ans);
    }
    return 0;
}