小 P 的星空

· · 题解

这里是出题人（

以 x 轴正半轴为起点，将所有星星逆时针排序，注意处理不同象限的星星的大小关系，询问直接在排序后的序列中二分查询位置，通过做差得到星星的数量。

本题难度不大，需要注意细节部分处理，部分分给得很多，本题目标就是提高本场比赛平均分，定位为 CSP-S2020 T2.

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
int n, m;

struct point {
    int x, y; //横坐标，纵坐标的绝对值
    int c; //区域
    bool operator<(const point& p) const {
        if (c != p.c) return c < p.c; //区域不同直接比较
        if (c % 2 == 0) return false; //坐标轴上不交换　
        if (c == 1 || c == 5) return (long long)x * p.y > (long long)y* p.x; //一三象限
        else return (long long)x * p.y < (long long)y * p.x; //二四象限
    }
} a[maxn], p;

point change(int x, int y) //化归操作
{
    point a;
    a.x = abs(x), a.y = abs(y);
    if (y == 0) a.c = x > 0 ? 0 : 4;  //x正/负半轴
    else if (x == 0) a.c = y > 0 ? 2 : 6; //y正/负半轴
    else if (x > 0) a.c = y > 0 ? 1 : 7;  //第一象限/第四象限
    else a.c = y > 0 ? 3 : 5;  //第二象限/第三象限
    return a;
}

struct line {
    int s, t, w;
};

line getline(point x)
{
    line res;
    res.s = lower_bound(a + 1, a + n + 1, x) - a;   //>=x的第一个元素 
    res.t = upper_bound(a + 1, a + n + 1, x) - a - 1;  //>x的第一个元素 
    res.w = res.t - res.s + 1; //线上有多少星星 
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= n; i++) {
        scanf("%d%d", &x, &y);
        a[i] = change(x, y);
    }
    sort(a + 1, a + n + 1);
    line u = getline(change(1, 0));
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        line v = getline(change(x, y));
        int num = v.s - u.t - 1; //求出一个某一个方向转动的星星 
        if (num < 0) num += n;
        printf("%d\n", max(n - num, num + u.w + v.w)); //全局减，得到另一方向的星星数量 
        u = v;
    }
}