2 solutions

  • 1
    @ 2022-9-11 22:07:22

    我们将一个人的成绩对应到三维空间中的位置向量,pi=(x,y,z)\vec p_i=(x,y,z),一种排名的计算步骤被抽象为

    1. 确定一个法向量v\vec v , 这个法向量需要满足这些条件:
    • vv>0\vec v \cdot \vec v > 0
    • v\vec v指向第一卦限(v[0],v[1],v[2]0\vec v[0],\vec v[1],\vec v[2]\ge 0)
    1. $\text{GPA}_i=v[0]p[0]+v[1]p[1]+v[2]p[2]=\vec v \cdot \vec p_i$,随后就可以得到小林排名。

    为什么这里不需要限制v[0]+v[1]+v[2]=1v[0]+v[1]+v[2] = 1呢?这是因为只要v[0]+v[1]+v[2]0v[0]+v[1]+v[2] \neq 0,计算出来的GPA只是等比例放大缩小,不影响排名。

    设小林的位置向量是Q\vec Q,利用v\vec v当作平面的法向量,可以确定一个过Q\vec Q点的平面F(v)\mathbb F(\vec v)(关于v\vec v的函数)。

    虽然F(v)\mathbb F(\vec v)千变万化,但是我们并不需要考虑那么多的情况,实际上我们只需要考虑:

    • F(v)\mathbb F(\vec v)经过包括QQ点的至少三个点
    • v=x or y or z\vec v=x \text{ or } y \text{ or } z

    rank(F)\text{rank}(\mathbb F)表示如果确定平面是F\mathbb F,小林的排名是多少,我们发现使得小林排名最高的F\mathbb F中,一定至少有一个F0\mathbb F_0经过了包括QQ点的至少三个点,即"临界条件"(使得rank(F)\text{rank}(\mathbb F)变化)。

    而还有三个临界条件,分别就是Oxy,Oyz,OxzOxy,Oyz,Oxz

    此时O(n3)O(n^3)算法就有了,枚举两个点R,SR,S,法向量就是n=RQ×SQ\vec n=\vec {RQ} \times \vec {SQ}(或者n-\vec n),然后计算所有人的GPA得到小林的排名。记得把v=(1,0,0),(0,1,0),(0,0,1)\vec v=(1,0,0),(0,1,0),(0,0,1)这几种情况考虑进去。

    mm维的情况也有对应的O(nm)O(n^m)的算法。这启示我们一件事,确定评价标准是一个非常主观的事情,可以让你高也让你低。所以最重要的还是是学到真正的本事。

    #ifndef H1__
    #define H2__
    #include<bits/stdc++.h>
    using namespace std;
    int qr(){
    	int ret=0,c=getchar();
    	while(!isdigit(c)) c=getchar();
    	while( isdigit(c)) ret=ret*10+c-48,c=getchar();
    	return ret;
    }
    using ll = long long;
    int n;
    const int maxn=5050+5;
    
    struct NODE{
    	ll x,y,z;
    	NODE():x(),y(),z(){}
    	NODE(const ll&a,const ll&b,const ll&c):x(a),y(b),z(c){}
    	NODE(const NODE&a):x(a.x),y(a.y),z(a.z){}
    	NODE operator - (const NODE&a)const{
    		return NODE(x-a.x,y-a.y,z-a.z);
    	}
    	NODE operator - ()const{
    		return NODE(-x,-y,-z);
    	}
    	NODE operator % (const NODE&a)const{
    		const ll&X=a.x;
    		const ll&Y=a.y;
    		const ll&Z=a.z;
    		return NODE(y*Z-z*Y,-x*Z+z*X,x*Y-y*X);
    	}
    	long long operator * (const NODE&a)const{
    		return x*a.x+y*a.y+z*a.z;
    	}
    	long long&operator[](const int&a){
    		assert(0<=a&&a<=2);
    		if(a==0) return x;
    		else if(a==1) return y;
    		else return z;
    		//impossible case
    	}
    	NODE&operator = (const NODE&a){
    		x=a.x; y=a.y; z=a.z;
    		return *this;
    	}
    }dat[maxn];
    
    int calc(NODE normal){
    	if(normal[0]<0||normal[1]<0||normal[2]<0)
    		normal=-normal;
    	if(normal[0]<0||normal[1]<0||normal[2]<0)
    		return n;
    	if(normal*normal==0)
    		return n;
    	ll proj=normal*dat[1];
    	int cnt=0;
    	for(int t=2;t<=n;++t)
    		if(normal*dat[t]<=proj)
    			++cnt;
    	return n-cnt;
    }
    
    int main(){
    	n=qr();
    	for(int t=1;t<=n;++t){
    #ifdef H1__
    		int x=qr(),y=qr(),z=0;
    #else
    		int x=qr(),y=qr(),z=qr();
    #endif
    		dat[t]=NODE(x,y,z);
    	}
    	NODE vec=dat[2]-dat[1];
    	int f=1;	
    	for(int t=2;t<=n;++t)
    		if(vec%(dat[t]-dat[1])*(vec%(dat[t]-dat[1])))
    			f=0;
    	// if(vec[0]>=0&&vec[1]>=0&&vec[2]>=0) return cout<<n<<endl,0;
    	// vec=-vec;
    	// if(vec[0]>=0&&vec[1]>=0&&vec[2]>=0) return cout<<n<<endl,0;
    	if(f) return puts("1"),0;
    #ifdef H1__
    	NODE v2=NODE(0,0,1);
    	int ans=n;
    	for(int t=2;t<=n;++t){
    		NODE v1=dat[t]-dat[1];
    		NODE normal=v1%v2;
    		//cerr<<normal[0]<<' '<<normal[1]<<endl;
    		ans=min(ans,calc(normal));
    	}
    	//cerr<<"H1__"<<endl;		
    #else
    	int ans=n;
    	for(int t=2;t<=n;++t){
    		for(int i=2;i<=n;++i){
    			NODE v1=dat[t]-dat[1],v2=dat[i]-dat[1];
    			NODE normal=v1%v2;
    			//cerr<<normal[0]<<' '<<normal[1]<<endl;
    			//cerr<<v1[0]<<' '<<v1[1]<<' '<<v1[2]<<endl;
    			ans=min(ans,calc(normal));
    		}
    	}	
    	//cerr<<"!H1__"<<endl;
    #endif
    	ans=min({ans,calc({1,0,0}),calc({0,1,0}),calc({0,0,1})});
    	cout<<ans<<endl;
    	return 0;
    }
    #undef H1__
    #endif
    

    Information

    ID
    160
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    (None)
    # Submissions
    242
    Accepted
    16
    Uploaded By