解题思路：

紫书上的里例题。

关键是能把问题转化为求半平面，并且确定删除x点是连续删除的，且不确定具体删除的是哪x个点，所以需要判断每x个点组成的凸多边形的半平面交是否为空，这个半平面交就可以安放总部的区域。因为x的值不确定，可以0-n二分判定，注意二分的写法！输入的点是顺时针的，要转为逆时针！

代码：

代码re了。。我不想改了。。等会再改

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxn = 5e4+10;
struct Point
{
    double x,y;
    Point(double x=0, double  y=0):x(x),y(y){}
};
typedef Point Vector;
int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    else return x > 0 ? 1 : -1;
}
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);
}
double Cross(Vector a, Vector b)//外积
{
    return a.x * b.y - a.y * b.x;
}
double Dot(Vector a, Vector b)//点积
{
    return a.x * b.x + a.y * b.y;
}
double Length(Vector a)//模
{
    return sqrt(Dot(a, a));
}

struct Line{
    Point p;//直线上任意一点
    Vector v;//方向向量
    double ang;//极角
    Line(){}
    Line(Point p, Vector v):p(p),v(v){ang = atan2(v.y,v.x);}
    friend bool operator < (Line a, Line b)
    {
        return a.ang < b.ang;
    }
};
bool OnLeft(Line L, Point p)
{
    return dcmp(Cross(L.v, p-L.p)) > 0 || dcmp(Cross(L.v, p-L.p)) == 0;
}
Point GetIntersection(Line a, Line b)
{
    Vector u = a.p-b.p;
    double t = Cross(b.v,u)/Cross(a.v,b.v);
    return a.p+a.v*t;
}
int HalfplaneIntersection(Line *L, int n, Point * poly)
{
    sort(L, L+n);//按极角排序
    int first, last;//指向双端队列的第一个元素和最后一个元素
    Point *p = new Point[n];//p[i]为q[i]和q[i+1]的交点
    Line *q = new Line[n];//双端队列
    q[first=last=0] = L[0];
    for(int i = 1; i < n; i++)
    {
        while(first < last && !OnLeft(L[i], p[last-1])) last--;
        while(first < last && !OnLeft(L[i], p[first])) first++;
        q[++last] = L[i];
        if(fabs(Cross(q[last].v,q[last-1].v)) < eps)//两向量平行且同向，取内侧的一个
        {
            last--;
            if(OnLeft(q[last],L[i].p)) q[last] = L[i];
        }
        if(first < last) p[last-1] = GetIntersection(q[last-1],q[last]);
    }
    while(first < last && !OnLeft(q[first], p[last-1])) last--;//删除无用平面
    if(last - first <= 1) return 0;
    p[last] =GetIntersection(q[last], q[first]);//首位半平面的交点
    int m = 0;
    for(int i = first; i <= last; i++) poly[m++] = p[i];
    return m;

}
Point p[maxn], poly[maxn];//p存输入的点， poly存半平面交上的点
Line L[maxn];
int  n;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    while(scanf("%d", &n))
    {
        if(n == 0) break;
        for(int i = n-1; i >= 0; i--) scanf("%lf %lf", &p[i].x, &p[i].y);//顺时针给出点
        int l = 0, r = n;
        while(l < r)
        {
            int mid = (l+r) >> 1;
            int num = 0;
            for(int i = 0; i < n; i++)
                L[num++] = Line(p[i], p[(i+mid+1)%n]-p[i]);
            int m = HalfplaneIntersection(L, num, poly);
            if(m == 0) r = mid;
            else l = mid+1;
        }
        printf("%d\n", l);
    }
    return 0;
}