poj3968

source: http://poj.org/problem?id=3968

title: Jungle Outpost

题目简意：给出一个凸多边形，求至少删除多少个点后，多边形内的任意一点都得不到庇护。

/*
可以肯定，被移除的 这些点在凸多边形上是连续的，于是可以二分至少需要移除的点数k，然后
用ps[i]->ps[(i+mid+1)%n](0<=i<n)构造n条线段，对这n条线段代表的 半平面求交，
最后判断求出来的凸多边形的面积是否为0即可。 
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=50005;
const double eps=1e-8;
int sign(double d){
	return d<-eps ? -1 : (d > eps);
}
struct point{
	double x, y;
	point(double _x=0, double _y=0):x(_x), y(_y){}
	void read(){
		scanf("%lf%lf", &x, &y);
	}
	void set(double _x, double _y){
		x=_x;
		y=_y;
	}
}ps[N], hull[N], pque[N];
struct seg{
	point st, ed;
	double ang;
	void calang(){
		ang = atan2(ed.y-st.y, ed.x-st.x);
	}
}sque[N+10], segs[N+10];
int n;
inline double xmul(point st1, point ed1, point st2, point ed2){
	return (ed1.x - st1.x) * (ed2.y - st2.y) - (ed1.y - st1.y) * (ed2.x - st2.x);
}
point intersectPoint(point st1, point ed1, point st2, point ed2){  //求相交直线的交点
	double t = xmul(st2, st1, st2, ed2) / ((ed1.y-st1.y) * (ed2.x-st2.x) - (ed1.x-st1.x) * (ed2.y-st2.y));
	return point(st1.x+(ed1.x-st1.x)*t, st1.y+(ed1.y-st1.y)*t);
}
bool cmpseg(seg a, seg b){
	return a.ang < b.ang;
}
//半平面交，第i个 半平面为segs[i].st->segs[i].ed的右侧，结果放在ps中确保不要有极端的 数据
//比如 相邻的 线段 虽然极角不一样但却平行！
void halfPlaneInter(seg* segs, int sn, point* ps, int& pn){
	int i, l, r;
	//由于问题的特殊性，这些线段已经是 有序的 了，并且不会有有两条线段极角相同
	if(sn <= 0){
		pn = 0;
		return;
	}
	if(sn <= 2){
		segs[sn] = segs[0];
		for(l = r = 0; r < sn; r++){
			sque[r] = segs[r];
			pque[r] = intersectPoint(segs[r].st, segs[r].ed, segs[r+1].st, segs[r+1].ed);
		}
	}else{
		l = r = 0;
		sque[r++] = segs[0];
		sque[r++] = segs[1];
		pque[0] = intersectPoint(sque[0].st, sque[0].ed, sque[1].st, sque[1].ed);
		for(i = 2; i < sn; i++){
			while(r-l >= 2 && sign(xmul(segs[i].st, segs[i].ed, segs[i].st, pque[r-2])) <= 0) r--;
			sque[r++] = segs[i];
			pque[r-2] = intersectPoint(sque[r-2].st, sque[r-2].ed, sque[r-1].st, sque[r-1].ed);
		}
		//删除多余的 半平面
		while(r-l >= 2){
			bool flag = false;
			if(sign(xmul(sque[r-1].st, sque[r-1].ed, sque[r-1].st, pque[l])) <= 0){
				flag = true;
				l++;
			}
			if(sign(xmul(sque[l].st, sque[l].ed, sque[l].st, pque[r-2])) <= 0){
				flag = true;
				r--;
			}
			if(!flag) break;
		}
		//这里需要注意，最后的结果可能是一个无限平面.
		pque[r-1] = intersectPoint(sque[l].st, sque[l].ed, sque[r-1].st, sque[r-1].ed);
	}
	for(pn = 0, i = l; i < r; i++){
		ps[pn++] = pque[i];
	}
}

bool input(){
	if(scanf("%d", &n)==EOF) return false;
	int i;
	for(i=0; i<n; i++){
		ps[n-i-1].read();  //保证输入的点是逆时针的
	}
	return true;
}
double area(point* ps, int pn){
	if(pn<=1) return 0;
	int i;
	double ans;
	for(ps[pn]=ps[0], ans=i=0; i<pn; i++){
		ans += (ps[i].x*ps[i+1].y-ps[i].y*ps[i+1].x);
	}
	return ans*0.5;
}
bool check(int mid){
	int hn, i;
	for(i=0; i<n; i++){
		segs[i].st=ps[i];
		segs[i].ed=ps[(i+mid+1)%n];
	}
	halfPlaneInter(segs, n, hull, hn);
	double s=area(hull, hn);
	return sign(s)==0;
}
void solve(){
	int l, r, mid;
	l=1;
	r=(n-1)>>1;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	int ans=r+1;
	printf("%d\n", ans);
}
int main(){
	while(input()) solve();
	return 0;
}