bzoj 4880 [Lydsy1705月赛]排名的战争贪心

[Lydsy1705月赛]排名的战争

Time Limit: 8 Sec Memory Limit: 256 MB
Submit: 338 Solved: 69
[Submit][Status][Discuss]

Description

小Q是一名出色的质检员，他负责质检一批手机的质量。手机包含两个性能属性：电池寿命x_1与坚硬度x_2。小Q将

为它们评估综合质量分数，具体地说，他将选择两个非负实数w_1,w_2，且$_1,w_2不能同时为0，则一部手机的综

合分数s=w_1*x_1+w_2*x_2。在评定出所有手机的分数后，小Q会把手机按分数从高到低排序，若有多部手机分数相

同，他可以将它们随意排列，因此每部手机的排名都是独一无二的。聪明的你会发现，对于不同的w的选定，手机

的最终排名可能会大不一样。因此各个公司都会暗中贿赂小Q，希望他让自己的排名尽量靠前。现一共有n家公司，

每家公司提供了一部手机用于质检。tangjz知道小Q可以通过调参来控制排名，所以他想知道他的公司的手机排名

最高是多少，最低是多少。

Input

第一行包含一个正整数n(1<=n<=100000)，即公司的个数。

接下来n行，每行两个正整数x_1,x_2(1<=x_1,x_2<=1000)，分别表示每部手机的两个属性。

tangjz所在公司提供的手机总是输入里的第一部手机。

Output

输出一行两个整数，即最高排名与最低排名。

Sample Input

5
7 7
11 10
8 5
1 1
12 12

Sample Output

3 4

HINT

Source

本OJ付费获得

只和w1，w2比值有关，那么就可以固定w2，然后不断调大w1就可以了

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<ctime>

 #include<cmath>

 #include<algorithm>

 #include<iomanip>

 #include<queue>

 #include<map>

 #include<bitset>

 #include<stack>

 #include<vector>

 #include<set>

 using namespace std;

 #define MAXN 100010

 #define MAXM 1010

 #define INF 1000000000

 #define MOD 1000000007

 #define ll long long

 #define eps 1e-8

 struct data{

     double v;

     int c;

     friend bool operator <(data x,data y){

         return x.v<y.v;

     }

 };

 int n;

 int x[MAXN],y[MAXN];

 int low=,high=INF;

 data t[MAXN];

 int tot;

 int main(){

     int i;

     scanf("%d",&n);

     for(i=;i<=n;i++){

         scanf("%d%d",&x[i],&y[i]);

     }

     int tlowx=,thighx=,tlowy=,thighy=;

     for(i=;i<=n;i++){

         if(x[i]>x[]){

             thighx++;

         }

         if(x[i]>=x[]){

             tlowx++;

         }

         if(y[i]>y[]){

             thighy++;

         }

         if(y[i]>=y[]){

             tlowy++;

         }

     }

     low=max(low,max(tlowx,tlowy));

     high=min(high,min(thighx,thighy));

     int tlow=,thigh=;

     for(i=;i<=n;i++){

         if(y[i]==y[]){

             if(x[i]>=x[]){

                 tlow++;

             }

             if(x[i]>x[]){

                 thigh++;

             }

             continue ;

         }

         if(y[i]<y[]){

             t[++tot].v=.*(x[]-x[i])/(y[i]-y[]);

             t[tot].c=-;

             tlow++;

             thigh++;

         }

         if(y[i]>y[]){

             t[++tot].v=.*(x[]-x[i])/(y[i]-y[]);

             t[tot].c=;

         }

         if(t[tot].v<=){

             tlow+=t[tot].c;

             thigh+=t[tot].c;

             tot--;

         }

     }

     if(tot){

         sort(t+,t+tot+);

         for(i=;i<=tot;){

             int wzh=i;

             int tc0=,tc1=;

             while(wzh<=tot&&fabs(t[wzh].v-t[i].v)<eps){

                 if(t[wzh].c==){

                     tc1++;

                 }else{

                     tc0++;

                 }

                 wzh++;

             }

             low=max(low,tlow+tc1);

             high=min(high,thigh-tc0);

             tlow+=tc1-tc0;

             thigh+=tc1-tc0;

             i=wzh;

         }

     }

     printf("%d %d\n",high,low);

 }

巴特西

bzoj 4880 [Lydsy1705月赛]排名的战争贪心

[Lydsy1705月赛]排名的战争

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

bzoj 4880 [Lydsy1705月赛]排名的战争 贪心

[Lydsy1705月赛]排名的战争

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

bzoj 4880 [Lydsy1705月赛]排名的战争贪心