补题：HOJ吉林selection B-Bribing Eve(Gym-101174B) (象限极角排序）

╰半夏微凉° 2022-05-14 08:27 139阅读 0赞

题目链接：  
[Gym-101174B][]

题目大意：  
给出n个序列对(x1,x2)，再给出一对（w1,w2)，定义Si = w1\*xi1+w2\*xi2 , 然后对Si进行从大到小排序，求S1最好与最坏的排位分别是多少？

解题思路：  
一开始，拿到这题第一想法就是贪心，对其中有一个大于第一个（x1,x2)，另一个小于第一个(x1,x2)的序列对贪心（比较大于x1的有多少，大于x2的有多少，然后取两者大的那个），但是一直WA，后面想想确实不能这样贪，不能取得最优解。

于是正解是转换为平面几何问题，已第一个点为坐标中心，将其他点放置在该坐标系上  
如图（‘x’ 就是第一个点对）：  
![这里写图片描述][70]  
转换之后，可以知道，在第一象限的点对，不管w1,w2取任意非负值，肯定大于’坐标原点‘  
在第三象限的点肯定小于’坐标原点‘，而第二和第四象限的点就是可调整区域。当然目前这个图中在y轴右边的都是大于原点的

那么我们将二四象限的点对于原点求极角，把角度从小到大排序，然后依次旋转y轴至最近的一个点，记录在y轴右边的最小最大点对数量就是答案！！！

AC代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    using namespace std;
    
    const double PI = acos(-1);
    const double eps = 1e-10;
    const int MAXN = 1e5+7;
    
    int sgn(double a, double b){
        if(fabs(a-b) < eps) return 0;
        return a < b ? -1 : 1;
    }
    
    double ang[MAXN], p[MAXN];
    
    int n,cnt,same,top,ansa,ansb;
    
    void solve(){
        int l = 1, r = 1;
        for(int i=1; i<=top; ++i){
            double d1 = p[i] + PI/2.0;
            double d2 = p[i] - PI/2.0;
            int tl = l, tr = r;
    
            while(r<=cnt && sgn(ang[r], d1)<=0) r++;
            r--;
            while(l <=r && sgn(ang[l],d2)<0) l++;
            while(tr<=cnt && sgn(ang[tr],d1)<0) tr++;
            tr--;
            while(tl<=tr && sgn(ang[tl],d2)<=0) tl++;
            ansb=max(ansb,r-l+1);
            ansa=min(ansa,tr-tl+1);
            tr++; 
        }
    }
    
    int main(int argc, char const *argv[])
    {
        cin>>n;
        cnt = top = 0;
        ansa = 0x3f3f3f3f; ansb = -1;
        int sx,sy;
        scanf("%d%d",&sx,&sy);
        for(int i=1; i<n; ++i){
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==sx && y==sy) {
                same++;
                continue;
            }
    
            ang[++cnt] = atan2(y-sy, x-sx);
            if(sgn(ang[cnt], PI/2.0) >=0 && sgn(ang[cnt], PI) <=0) p[++top] = ang[cnt] - PI/2.0;
            if(sgn(ang[cnt], -PI/2.0) >=0 && sgn(ang[cnt], 0.0) <=0) p[++top] = ang[cnt] + PI/2.0;
        }
    
        sort(ang+1,ang+cnt+1);
        sort(p+1,p+top+1);
    
        solve();
        if(top==0) cout<<"1 1"<<endl;
        else cout<<ansa+1<<" "<<ansb+1+same<<endl;
        return 0;
    }

[Gym-101174B]: https://vjudge.net/problem/Gym-101174B
[70]: /images/20220514/7e259a5187ff45a99f6ef5655fed3692.png