Gym-101174B Bribing Eve （象限极角排序）

46 阅读 0 评论 31 点赞

我是靠谱客的博主冷傲糖豆，最近开发中收集的这篇文章主要介绍Gym-101174B Bribing Eve （象限极角排序），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Bribing Eve
Eve works at a magazine that does product reviews and publishes
recommendations to consumers. They are working on a
new mobile phones review and have decided on two reproducible
tests that score each device's battery lifetime and performance
using an integer between 1 and 1000.
These two scores, x1 and x2, are then combined with a weights
vector w = [w1, w2] to produce an overall score:
s = w1x1 + w2x2 .
The nal review ranking is then obtained by sorting the products
by decreasing order of s. Additionally, when multiple products
get exactly the same score, Eve decides how to order them.
Maria (a fake name to mask her identity) tried to bribe Eve to tweak the results to get her
product higher on the list. Eve argued that she was not able to tamper the evaluation of each
test, but Maria suggested to tweak the weights w used when computing the overall score. The
weights w must be non-negative and at least one of them must be positive, but the values are
decided by Eve.
Eve is thinking whether to modify the weights in Maria's benet or not, and asked you to
determine what are the best and worst possible ranking positions for Maria's product.
Task
Given a list of all products scores in battery and performance [x1, x2] tests, nd out what are
the best and worst positions in the ranking that can be given to Maria's product when the
weights [w1, w2] and the order for tied products are left for Eve to decide.
Input
The rst line has the number N of products being compared. N lines follow, each containing
two integers x1 and x2 indicating a product's score in the battery and performance tests.
Maria's product is the rst on the list.
Constraints
1 ≤ N ≤ 100 000 Number of products
1 ≤ x1, x2 ≤ 1 000 Performance of a product in the tests
SWERC'2016 Universidade do Porto 5
Problem B Problem B
Output
The output consists of two numbers A and B, indicating the best and worst possible positions
that Maria's product can get on the ranking given Eve's ability to modify the weights and
ordering in case of a tie.
Sample Input
5
7 7
11 10
8 5
1 1
12 12
Sample Output

3 4

题解：考虑函数的几何意义，枚举向量，使用象限极角排序+二分查找，其实不用二分也可以。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-9;
struct point
{
int x,y;
}pp[100005];
typedef point Vector;
Vector vc[100005];
int sum1=0,sum2=0,sum3=0,sum4=0;
double dot(Vector a,Vector b)
{
return 1.0*a.x*b.y-1.0*a.y*b.x;
}
int quad(Vector a)// 判断象限的函数，每个象限包括半个坐标轴
{
if( a.x>=0 && a.y>0 ) return 1;
if( a.x<0 && a.y>=0 ) return 2;
if( a.x<=0 && a.y<0 ) return 3;
if( a.x>0 && a.y<=0 ) return 4;
}
bool operator < (const Vector &a,const Vector &b)
{
Vector p1 = a,p2 = b;
int l1,l2;
l1 = quad(p1); l2 = quad(p2);
if( l1 == l2 )
{
if(dot(a,b)>0)
return true;
else
return false;
}
return l1 < l2;
}
int main()
{
int n;
cin>>n;
int sum5=0;
for(int i=0;i<n;i++)
{
scanf("%d %d",&pp[i].x,&pp[i].y);
vc[i].x=pp[i].x-pp[0].x,vc[i].y=pp[i].y-pp[0].y;
if(vc[i].x==0&&vc[i].y==0){
vc[i].x=vc[i].y=1;
sum5++;
}
if(i==0)
continue;
if(vc[i].x>=0)
sum1++;
if(vc[i].x>0)
sum2++;
if(vc[i].y>=0)
sum3++;
if(vc[i].y>0)
sum4++;
}
sort(vc+1,vc+n);
/*for(int i=1;i<n;i++)
cout<<vc[i].x<<' '<<vc[i].y<<endl;*/
int ans1=0,ans2=10000000;
for(int i=1;i<n;i++)
{
if((vc[i].x<=0&&vc[i].y>=0))
{
//cout<<i<<endl;
Vector a;
a.x=-1*vc[i].x,a.y=-1*vc[i].y;
int c=lower_bound(vc+1,vc+n,a)-vc;
int d=upper_bound(vc+1,vc+n,a)-vc;
int now=i;
if(c>=i)now+=n-1;
else if(d>=i)now+=n-1;
//cout<<c<<d<<endl;
ans1=max((now-c+1)+1,ans1);
ans2=min((now-d+1-sum5)+1,ans2);
//cout<<c<<' '<<d<<' '<<i<<' '<<ans1<<' '<<ans2<<endl;
}
else
continue;
}
ans1=max(ans1,sum1+1);
ans1=max(ans1,sum3+1);
ans2=min(ans2,sum2+1);
ans2=min(ans2,sum4+1);
cout<<ans2<<' '<<ans1<<endl;
//cout << "Hello world!" << endl;
return 0;
}