自动搬运

查看原文

来自洛谷，原作者为

	tuxiaobei **

搬运于2025-08-24 22:26:56，当前版本为作者最后更新于2020-11-27 21:40:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是出题人（

以 $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;
	}
}