地址：http://codeforces.com/gym/101174/attachments
题目：pdf，略
思路：
把每个人的(x1,x2)抽象成点(xi,yi).
当1号比i号排名高时有==>a(x1-xi)+b(y1-yi)>=0
把(x1-xi,y1-yi)看着向量，(a,b)看做向量。则和(a,b)夹角在90度内的向量个数就是不如1号点优的个数。
所以要使1号得到最高排名就是使和(a,b)夹角在90度内（包括90度）的向量个数最大。
所以要使1号得到最低排名就是使和(a,b)夹角在90度内（不包括90度）的向量个数最小。
注意特判掉xi==x1 && yi==y1的点，以及(a,b)只能在第一象限内。
求解最高or低排名的过程：
把所有向量求个极角，然后极角排序。扫一遍有用的可能的(a,b)向量，中间利用two point的方法维护答案。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define MP make_pair 6 #define PB push_back 7 typedef long long LL; 8 typedef pair<int,int> PII; 9 const double eps=1e-8; 10 const double pi=acos(-1.0); 11 const int K=1e5+7; 12 const int mod=1e9+7; 13 14 double angle[K],tmp[K]; 15 int n,m,ansa,ansb=K; 16 int sgn(double ta,double tb) 17 { 18 if(fabs(ta-tb)<eps) return 0; 19 return ta<tb?-1:1; 20 } 21 int sc(void) 22 { 23 int l=1,r=0; 24 double nt1,nt2; 25 for(int i=0;i<m;i++) 26 { 27 int tl=l,tr=r; 28 nt1=tmp[i]+pi/2.0; 29 nt2=tmp[i]-pi/2.0; 30 31 while(r<n-1 && sgn(angle[r+1],nt1)<=0) r++; 32 while(l<=r && sgn(angle[l],nt2)<0) l++; 33 while(tr && sgn(angle[tr],nt1)==0) tr--; 34 while(tr<n-1 && sgn(angle[tr+1],nt1)<0) tr++; 35 while(tl<=tr && sgn(angle[tl],nt2)<=0) tl++; 36 ansa=max(ansa,r-l+1); 37 ansb=min(ansb,tr-tl+1); 38 tr++; 39 } 40 } 41 int main(void) 42 { 43 int sx,sy,tn=1,same=0; 44 scanf("%d",&n); 45 scanf("%d%d",&sx,&sy); 46 for(int i=2,x,y;i<=n;i++) 47 { 48 scanf("%d%d",&x,&y); 49 if(x==sx && y==sy) {same++;continue;} 50 angle[tn]=atan2(sy-y,sx-x); 51 if(sgn(angle[tn],pi/2.0)>=0 && sgn(angle[tn],pi)<=0) 52 tmp[m++]=angle[tn]-pi/2.0; 53 else if(sgn(angle[tn],-pi/2.0)>=0 && sgn(angle[tn],0.0)<=0) 54 tmp[m++]=angle[tn]+pi/2.0; 55 tn++; 56 } 57 n=tn; 58 sort(angle+1,angle+tn); 59 sort(tmp,tmp+m); 60 sc(); 61 printf("%d %d ",n-ansa,n-ansb+same); 62 return 0; 63 }