poj 1271 || UVA 10117 Nice Milk

午后は葛藤しましたね!!!タイムアウトだ!!!私はWSの方法で長い間また私の時間の複雑さを測りました!!!データの最后のグループに引っかかっているような気がします!!!
UVA waにいましたね!!!説明UVAマシンはPOJより速いですね!!!
考え方:牛乳をつける最大面積、つまり半平面交差後の中間領域が最小であることを求めるので、半平面交差中間の最小領域を求めるだけでよい.この実装にはDFS列挙が必要ですね.
ずっとTLEで、後でネットを見たのはやはりどこから手に入れたのか分かりません.後で最適化方法を思い出します.中のエッジは平行なので、中のエッジを選択すると、それでは、外の辺はいらない(ソートして削除するので)、そのままその辺をカバーすればいいし、時間も節約できる.すると、WA==後に2つのエラーが見つかり、入力は出力前にT T...出力0.00後に直接continue==後ACを変更した.
2つのコードはいずれもDFSの違いであり,1つは1つのエッジを見つけて追加し,k個の後に面積を求めることである.もう1つはDFSスキームをすべて列挙してから==..
1つ目は急いで、面積が0の私を見つけたら直接returnしたからです.また、選択する要素の数よりもオプションの要素が少ない場合はreturnになります.でも少なくとも600+MS...T T...
P.S.uniqueの削除を疑ったことがあります.半平面で交わると、初めて傾きが等しい点を削除すると、一番左の(一番左を有効方向と定義します)を残すべきだからです.uniqueがむやみに削除するのを恐れています.でも、さっきテストしましたが、uniqueが削除したのはすべて最初の要素なので、安心しました.
P.S.uniqueの内部実装を調べたばかりで、確かに最初の要素を残しています.ほほほ.

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>

using namespace std;

const int MAX = 25;
const double inf = 1e20;
struct point {double x,y;};
struct line { double ang; point a,b;};
point p[MAX],s[MAX];
line ln[MAX],deq[MAX],ltmp[MAX],ll[MAX],lk[MAX];;
double h,mmin;
const double eps = 1e-6;
int k;
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
double disp2p(point a,point b) //  a b         
{
	return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
}
double crossProduct(point a,point b,point c)//   ac   ab     
{
	return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
void changepoint(point a,point b,point &c,point &d)
{
	double len = disp2p(a,b);
    double dx = h / len * ( a.y - b.y );
	double dy = h / len * (-a.x + b.x );
	c.x = a.x + dx; c.y = a.y + dy;
	d.x = b.x + dx; d.y = b.y + dy;
}
void makeline_hp(point a,point b,line &l) //   (  ab)       
{
	l.a = a; l.b = b;
	l.ang = atan2(a.y - b.y,a.x - b.x);	//        ，  b.y - a.y,b.x - a.x 
}
bool equal_ang(line a,line b)	//    unique      
{
	return dd(a.ang,b.ang);
}
bool cmphp(line a,line b)	//         
{
	if( dd(a.ang,b.ang) ) return xy(crossProduct(b.a,b.b,a.a),0.0);
	return xy(a.ang,b.ang);
}
bool equal_p(point a,point b)//   unique      
{
	return dd(a.x,b.x) && dd(a.y,b.y);
}
bool parallel(line u,line v)
{
	return dd( (u.a.x - u.b.x)*(v.a.y - v.b.y) - (v.a.x - v.b.x)*(u.a.y - u.b.y) , 0.0 );
}
point l2l_inst_p(line l1,line l2)
{
	point ans = l1.a;
	double t = ((l1.a.x - l2.a.x)*(l2.a.y - l2.b.y) - (l1.a.y - l2.a.y)*(l2.a.x - l2.b.x))/
			   ((l1.a.x - l1.b.x)*(l2.a.y - l2.b.y) - (l1.a.y - l1.b.y)*(l2.a.x - l2.b.x));
	ans.x += (l1.b.x - l1.a.x)*t;
	ans.y += (l1.b.y - l1.a.y)*t;
	return ans;
}
double area_polygon(point p[],int n)
{
	double s = 0.0;
	for(int i=0; i<n; i++)
		s += p[(i+1)%n].y * p[i].x - p[(i+1)%n].x * p[i].y;
	return fabs(s)/2.0;
}
void inst_hp_nlogn(line *ln,int n,point *s,int &len)
{
	len = 0;
	sort(ln,ln+n,cmphp);
	n = unique(ln,ln+n,equal_ang) - ln;
	int bot = 0,top = 1;
	deq[0] = ln[0]; deq[1] = ln[1];
	for(int i=2; i<n; i++)
	{
		if( parallel(deq[top],deq[top-1]) || parallel(deq[bot],deq[bot+1]) )
			return ;
		while( bot < top && dy(crossProduct(ln[i].a,ln[i].b,
			l2l_inst_p(deq[top],deq[top-1])),0.0) )
			top--;
		while( bot < top && dy(crossProduct(ln[i].a,ln[i].b,
			l2l_inst_p(deq[bot],deq[bot+1])),0.0) )
			bot++;
		deq[++top] = ln[i];
	}
	while( bot < top && dy(crossProduct(deq[bot].a,deq[bot].b,
		l2l_inst_p(deq[top],deq[top-1])),0.0) )	top--;
	while( bot < top && dy(crossProduct(deq[top].a,deq[top].b,
		l2l_inst_p(deq[bot],deq[bot+1])),0.0) )	bot++;
	
	if( top <= bot + 1 ) return ;
	
	for(int i=bot; i<top; i++)
		s[len++] = l2l_inst_p(deq[i],deq[i+1]);
	if( bot < top + 1 ) s[len++] = l2l_inst_p(deq[bot],deq[top]);
	len = unique(s,s+len,equal_p) - s;
}

void DFS(int x,int n,int sum)
{
	if( mmin == 0.0 ) return ;
	if( n - x < k - sum ) return ;
	if( sum == k )
	{
		int len;
		memcpy(ltmp,ln,sizeof(ln));
		inst_hp_nlogn(ltmp,n,s,len);
		mmin = min(mmin,area_polygon(s,len));
		if( mmin == 0.0 ) return ;
		return ;
	}
	for(int i=x; i<n; i++)
	{
		ln[i] = ll[i];
		DFS(i+1,n,sum+1);
		if( mmin == 0.0 ) return ;
		ln[i] = lk[i];
	}
}

int main()
{
	int n;
	
	while( ~scanf("%d%d%lf",&n,&k,&h) )
	{
		if( !(n || k || h) ) break;
		for(int i=0; i<n; i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		if( h == 0 || k == 0 )
		{
			printf("0.00
");
			continue;
		}
		p[n] = p[0];
		double area = area_polygon(p,n);
		for(int i=0; i<n; i++)
		{
			point c,d;
			changepoint(p[i],p[i+1],c,d);
			makeline_hp(c,d,ll[i]);
			makeline_hp(p[i],p[i+1],ln[i]);
		}
		memcpy(lk,ln,sizeof(ln));
		if( k > n ) k = n;
		mmin = inf;
		DFS(0,n,0);
		double ans = area - mmin;
		printf("%.2lf
",ans);
	}
return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>

using namespace std;

const int MAX = 25;
const double inf = 1e20;
const double pi = acos(-1.0);
struct point {double x,y;};
struct line { double ang; point a,b;};
point p[MAX],s[MAX];
line ln[MAX],deq[MAX],ltmp[MAX],ll[MAX];
double h,mmin;
const double eps = 1e-6;
int k,cnt;
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
double disp2p(point a,point b) //  a b         
{
	return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
}
double crossProduct(point a,point b,point c)//   ac   ab     
{
	return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
void changepoint(point a,point b,point &c,point &d)
{
	double len = disp2p(a,b);
    double dx = h / len * ( a.y - b.y );
	double dy = h / len * (-a.x + b.x );
	c.x = a.x + dx; c.y = a.y + dy;
	d.x = b.x + dx; d.y = b.y + dy;
}
void makeline_hp(point a,point b,line &l)
{
	l.a = a; l.b = b;
	l.ang = atan2(a.y - b.y,a.x - b.x);
}
bool equal_ang(line a,line b)	//    unique      
{
	return dd(a.ang,b.ang);
}
bool cmphp(line a,line b)	//         
{
	if( dd(a.ang,b.ang) ) return xy(crossProduct(b.a,b.b,a.a),0.0);
	return xy(a.ang,b.ang);
}
bool equal_p(point a,point b)//   unique      
{
	return dd(a.x,b.x) && dd(a.y,b.y);
}
bool parallel(line u,line v)
{
	return dd( (u.a.x - u.b.x)*(v.a.y - v.b.y) - (v.a.x - v.b.x)*(u.a.y - u.b.y) , 0.0 );
}
point l2l_inst_p(line l1,line l2)
{
	point ans = l1.a;
	double t = ((l1.a.x - l2.a.x)*(l2.a.y - l2.b.y) - (l1.a.y - l2.a.y)*(l2.a.x - l2.b.x))/
			   ((l1.a.x - l1.b.x)*(l2.a.y - l2.b.y) - (l1.a.y - l1.b.y)*(l2.a.x - l2.b.x));
	ans.x += (l1.b.x - l1.a.x)*t;
	ans.y += (l1.b.y - l1.a.y)*t;
	return ans;
}
double area_polygon(point p[],int n)
{
	if( n < 3 ) return 0.0;
	double s = 0.0;
	for(int i=0; i<n; i++)
		s += p[(i+1)%n].y * p[i].x - p[(i+1)%n].x * p[i].y;
	return fabs(s)/2.0;
}
line lk[MAX];
void inst_hp_nlogn(line *ln,int n,point *s,int &len)
{
	len = 0;
	sort(ln,ln+n,cmphp);
	n = unique(ln,ln+n,equal_ang) - ln;
	int bot = 0,top = 1;
	deq[0] = ln[0]; deq[1] = ln[1];
	for(int i=2; i<n; i++)
	{
		if( parallel(deq[top],deq[top-1]) || parallel(deq[bot],deq[bot+1]) )
			return ;
		while( bot < top && dy(crossProduct(ln[i].a,ln[i].b,
			l2l_inst_p(deq[top],deq[top-1])),0.0) )
			top--;
		while( bot < top && dy(crossProduct(ln[i].a,ln[i].b,
			l2l_inst_p(deq[bot],deq[bot+1])),0.0) )
			bot++;
		deq[++top] = ln[i];
	}
	while( bot < top && dy(crossProduct(deq[bot].a,deq[bot].b,
		l2l_inst_p(deq[top],deq[top-1])),0.0) )	top--;
	while( bot < top && dy(crossProduct(deq[top].a,deq[top].b,
		l2l_inst_p(deq[bot],deq[bot+1])),0.0) )	bot++;
	
	if( top <= bot + 1 ) return ;
	
	for(int i=bot; i<top; i++)
		s[len++] = l2l_inst_p(deq[i],deq[i+1]);
	if( bot < top + 1 ) s[len++] = l2l_inst_p(deq[bot],deq[top]);
	len = unique(s,s+len,equal_p) - s;
}
int t[150000][10];
int tt[10];
void DFS(int x,int n,int sum)
{
	if( n - x < k - sum ) return ;
	if( sum == k )
	{
		memcpy(t[cnt++],tt,sizeof(tt));
		return ;
	}
	for(int i=x; i<n; i++)
	{
		tt[sum] = i;
		DFS(i+1,n,sum+1);
	}
}

int main()
{
	int n,len;
	point c,d;
	while( ~scanf("%d%d%lf",&n,&k,&h) )
	{
		if( !(n || k || h) ) break;
		cnt = 0;

		for(int i=0; i<n; i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		if( h == 0 || k == 0 )
		{
			printf("0.00
");
			continue;
		}
		p[n] = p[0];
		double area = area_polygon(p,n);
		for(int i=0; i<n; i++)
		{
			changepoint(p[i],p[i+1],c,d);
			makeline_hp(c,d,ll[i]);
			makeline_hp(p[i],p[i+1],ln[i]);
		}
		if( k > n )	k = n;
		mmin = inf;
		DFS(0,n,0);
		for(int i=0; i<cnt; i++)
		{
			memcpy(ltmp,ln,sizeof(ln));
			for(int j=0; j<k; j++)
				ltmp[t[i][j]] = ll[t[i][j]];
			inst_hp_nlogn(ltmp,n,s,len);
			mmin = min(mmin,area_polygon(s,len));
			if( mmin == 0 )
				break;
		}
		double ans = area - mmin;
		printf("%.2lf
",ans);
	}
return 0;
}