2 solutions
-
1
我们将一个人的成绩对应到三维空间中的位置向量,,一种排名的计算步骤被抽象为
- 确定一个法向量, 这个法向量需要满足这些条件:
- 指向第一卦限()
- $\text{GPA}_i=v[0]p[0]+v[1]p[1]+v[2]p[2]=\vec v \cdot \vec p_i$,随后就可以得到小林排名。
为什么这里不需要限制呢?这是因为只要,计算出来的GPA只是等比例放大缩小,不影响排名。
设小林的位置向量是,利用当作平面的法向量,可以确定一个过点的平面(关于的函数)。
虽然千变万化,但是我们并不需要考虑那么多的情况,实际上我们只需要考虑:
- 经过包括点的至少三个点
设表示如果确定平面是,小林的排名是多少,我们发现使得小林排名最高的中,一定至少有一个经过了包括点的至少三个点,即"临界条件"(使得变化)。
而还有三个临界条件,分别就是。
此时算法就有了,枚举两个点,法向量就是(或者),然后计算所有人的GPA得到小林的排名。记得把这几种情况考虑进去。
维的情况也有对应的的算法。这启示我们一件事,确定评价标准是一个非常主观的事情,可以让你高也让你低。所以最重要的还是是学到真正的本事。
#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