Problem: Example

Input

6 5 1 2 3
5 5 5
1 5 5
2 5 4
3 5 3
4 5 2
5 5 1


Output

0.631579

Solution (in CPP):

Solution:
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

typedef double Real;
typedef vector<int> Vector;

const Real inf=1e12;
const Real eps=1e-9;

template<class T> bool eq(T a, T b){
	return abs(a-b)<eps;
}

template<class T> int sgn(T a){
	if(eq(a,0.0)) return 0;
	if(a>0) return 1;
	return -1;
}

Vector crP(Vector v1,Vector v2){
	Vector res;
	for(int i=0;i<3;i++){
		Real val=0;
		val+=v1[(i+1)%3]*v2[(i+2)%3];
		val-=v1[(i+2)%3]*v2[(i+1)%3];
		res.push_back(val);
	}
	return res;
}

Vector subt(Vector v1,Vector v2){
	Vector res;
	for(int i=0;i<3;i++){
		res.push_back(v1[i]-v2[i]);
	}
	return res;
}

struct Prod:Vector{
	int val;
	Prod(){}
//	Prod(int x,int y,int z):Vector({x,y,z}){}
	Prod(Vector v):Vector(v){}
};

bool operator<(const Prod &p1,const Prod &p2){
	return p1.val<p2.val;
}

Prod prods[55];
int N,K;
int A,B,C;

vector<Vector> all;

void solve(vector<Prod> prods,int K){
	if(K==0){
		vector<int> vec;
		for(int i=0;i<3;i++) vec.push_back(0);
		all.push_back(vec);
		return;
	}
	for(int i=0;i<prods.size();i++){
		for(int j=0;j<prods.size();j++) for(int k=0;k<prods.size();k++){
			if(i==j||j==k||k==i) continue;
			Vector v1=subt(prods[j],prods[i]);
			Vector v2=subt(prods[k],prods[i]);
			Vector n=crP(v1,v2);
			Prod tmp[55];
			for(int l=0;l<prods.size();l++){
				tmp[l]=prods[l];
				tmp[l].val=0;
				for(int x=0;x<3;x++) tmp[l].val+=prods[l][x]*n[x];
			}
			bool out=false;
			if(i==0&&j==1&&k==2) out=true;
			sort(tmp,tmp+prods.size());
			int sum[3]={};
			for(int l=0;l<K;l++){
				for(int x=0;x<3;x++){
					sum[x]+=tmp[l][x];
				}
			}
			all.push_back(Vector(sum,sum+3));
		}
	}
	Prod tmp[55];
	for(int i=0;i<prods.size();i++){
		for(int l=0;l<prods.size();l++){
			tmp[l]=prods[l];
			tmp[l].val=0;
			for(int x=0;x<3;x++) tmp[l].val+=prods[l][x];
		}
		sort(tmp,tmp+prods.size());
		int sum[3]={};
		for(int l=0;l<K;l++){
			for(int x=0;x<3;x++){
				sum[x]+=tmp[l][x];
			}
		}
		all.push_back(Vector(sum,sum+3));
	}
}

int main(){
	scanf("%d%d",&N,&K);
	if(N==K){
		printf("0\n");
		return 0;
	}
	scanf("%d%d%d",&A,&B,&C);
	for(int i=0;i<N;i++){
		int x[3];
		for(int j=0;j<3;j++){
			scanf("%d",x+j);
		}
		Vector v=Vector(x,x+3);
		prods[i]=v;
	}
	vector<Prod> prods1=vector<Prod>(prods+1,prods+N);
	solve(prods1,K);
	long long e=-1;
	for(int i=0;i<all.size();i++){
		long long cur=1;
		for(int j=0;j<3;j++) cur*=all[i][j];
		if(e<0||e>cur){
			e=cur;
		}
	}
//	printf("e=%lld\n",e);
	all.clear();
	solve(prods1,K-1);
	Real ans=-1;
	for(int i=0;i<all.size();i++){
		int a[3];
		for(int j=0;j<3;j++) a[j]=all[i][j];
		for(int s=0;s<3;s++) for(int t=0;t<3;t++) for(int u=0;u<3;u++){
			int cnt=0;
			if(s==2) cnt++;
			if(t==2) cnt++;
			if(u==2) cnt++;
			if(cnt!=1) continue;
			
			Real val=0;
			Real x=prods[0][0];
			Real y=prods[0][1];
			Real z=prods[0][2];
			Real nochange=(x+a[0])*(y+a[1])*(z+a[2]);
			if(sgn(nochange-e)<=0){
				printf("0\n");
				return 0;
			}
			if(s==0){
				val+=A;
				x=0;
			}
			if(t==0){
				val+=B;
				y=0;
			}
			if(u==0){
				val+=C;
				z=0;
			}
			
			if(s==2){
				Real tmp=e/(y+a[1])/(z+a[2]);
				tmp-=a[0];
				if(sgn(tmp)<0||sgn(tmp-x)>0) val+=inf;
				else val+=(Real)A*(x-tmp)/x;
			}else if(t==2){
				Real tmp=e/(z+a[2])/(x+a[0]);
				tmp-=a[1];
				if(sgn(tmp)<0||sgn(tmp-y)>0) val+=inf;
				else val+=(Real)B*(y-tmp)/y;
			}else{
				Real tmp=e/(x+a[0])/(y+a[1]);
				tmp-=a[2];
				if(sgn(tmp)<0||sgn(tmp-z)>0) val+=inf;
				else val+=(Real)C*(z-tmp)/z;
			}
			
			if(val<inf/2){
				if(ans<0||ans>val) ans=val;
			}
		}
	}
	printf("%.9f\n",ans);
	return 0;
}