Language: C++

#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cmath>
#include <climits>
#include <utility>

#include <bitset>
#include <iostream>

using namespace std;

#define EPS 1e-7

typedef vector<double> vdouble;
typedef complex<double> P;
typedef const P &rP;
typedef pair<double,int> pdi;


inline double dot(rP a, rP b){
	return real(a) * real(b) + imag(a) * imag(b);
}

inline double cross(rP a, rP b){
	return real(a) * imag(b) - imag(a) * real(b);
}

inline bool contain_s_p(rP a1, rP a2, rP b){
	return abs(abs(a1 - b) + abs(a2 - b) - abs(a1 - a2)) < EPS;
}

inline bool contain_hl_p(rP a1, rP a2, rP b){
	return contain_s_p(a1, a2, b) || contain_s_p(a1, b, a2);
}


inline vdouble intersect_hl_s(rP pa1, rP pa2, rP pb1, rP pb2){
	P da12 = pa2 - pa1;
	P db21 = pb1 - pb2;
	P dab1 = pb1 - pa1;

	double D = cross(da12, db21);
	
	vdouble ret;

	if(abs(D) > EPS){
		double t = cross(dab1, db21) / D;
		double s = cross(da12, dab1) / D;
		
		if( -EPS < t && (-EPS < s && s < 1.0 + EPS) ){
			ret.push_back(t);
			ret.push_back(s);
		}
	}
	else if(contain_hl_p(pa1, pa2, pb1)){
		ret.push_back(abs(dab1) / abs(da12));
		ret.push_back(0.0);
		ret.push_back(abs(pb2 - pa1) / abs(da12));
		ret.push_back(1.0);
	}
	return ret;
}

struct intrinfo{
	double t;
	int idx;
	double s;

	bool operator< (const intrinfo &i) const{
		return t < i.t;
	}
};

int n;
vector<P> plg;
double pi;

double checkarg(rP base, rP pa, rP pb, rP pc){
	double a = arg(pa - base);
	double b = arg(pb - base);
	double c = arg(pc - base);
	if(b + EPS < a) b += 2.0 * pi;
	if(c + EPS < a) c += 2.0 * pi;
	return a < b + EPS && b < c + EPS;
}

bool checkrange(vector<pdi> &v){
	v.push_back(pdi(0.5, 0));
	int m = v.size();
	sort(v.begin(), v.end());
	v.push_back(pdi(2.0, 0));

	int c = 0;
	for(int i = 0; i < m; ++i){
		if(v[i].first > 1.0 - EPS) return true;
		if(c == 0 && v[i].first > EPS){
			if(v[i+1].first - v[i].first > EPS){
				return false;
			}
		}

		c -= v[i].second;
	}
	return true;
}

int solve(){
	int ans = n;

	vector<vdouble> mins(n, vdouble(n, 2.0));
	vector<vdouble> maxs(n, vdouble(n, -1.0));
	
	//(plg[i], plg[j]) _ (plg[k], plg[k+1])
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(i == j){ continue; }
			if(!checkarg(plg[i], plg[i+1], plg[j], plg[(i-1+n)%n])){
				continue;
			}

			vector<intrinfo> v;
			int k = i;
			do{
				vdouble ret = intersect_hl_s(plg[i], plg[j], plg[k], plg[k+1]);

				for(int u = 0; u < ret.size(); u += 2){
					v.push_back((intrinfo){ret[u], k, ret[u+1]});
				}
				
				k = (k + 1) % n;
			} while(k != i);

			double cuts = DBL_MAX;
			double c1 = 1.0;
			for(k = 0; k < v.size(); ++k){
				double c2 = cross(plg[j] - plg[i], plg[v[k].idx + 1] - plg[i]);
				if(abs(c2) > EPS && c1 * c2 < 0.0){
					cuts = min(cuts, v[k].s);
					c1 = -c1;
				}
			}

			sort(v.begin(), v.end());
			for(k = v.size() - 1; k >= 0; --k){
				if(v[k].s < cuts + EPS){
					v[k].resize(k + 1);
					break;
				}
			}

			for(k = 0; k < v.size(); ++k){
				int q = v[k].idx;
				mins[i][q] = min(mins[i][q], v[k].s);
				maxs[i][q] = max(maxs[i][q], v[k].s);
			}
		}
	}

	for(int S = (1 << n) - 1; S > 0; --S){
		int cnt = 0;
		
		vector<vector<pdi> > imos(n);
		for(int i = 0; i < n; ++i){
			if(!(S >> i & 1)) continue;
			++cnt;

			for(int j = 0; j < n; ++j){
				if(mins[i][j] + EPS < maxs[i][j]){
					imos[j].push_back(pdi(mins[i][j], -1));
					imos[j].push_back(pdi(maxs[i][j], 1));
				}
			}
		}
		if(cnt >= ans) continue;

		bool ok = true;
		for(int i = 0; i < n; ++i){
			if(!checkrange(imos[i])){
				ok = false;
				break;
			}
		}

		if(ok){
			ans = cnt;
		}

	}
	return ans;
}

int main(){
	pi = acos(-1.0);

	double x, y;
	while(scanf("%d", &n), n){
		plg.resize(n + 1);
		for(int i = 0; i < n; ++i){
			scanf("%lf%lf", &x, &y);
			plg[i] = P(x, y);
		}
		plg[n] = plg[0];

		printf("%d\n", solve());
	}
}

Compiler output:
a.cc: In function 'int solve()':
a.cc:135:39: error: 'DBL_MAX' was not declared in this scope
  135 |                         double cuts = DBL_MAX;
      |                                       ^~~~~~~
a.cc:11:1: note: 'DBL_MAX' is defined in header '<cfloat>'; this is probably fixable by adding '#include <cfloat>'
   10 | #include <iostream>
  +++ |+#include <cfloat>
   11 | 
a.cc:148:46: error: '__gnu_cxx::__alloc_traits<std::allocator<intrinfo>, intrinfo>::value_type' {aka 'struct intrinfo'} has no member named 'resize'
  148 |                                         v[k].resize(k + 1);
      |                                              ^~~~~~