列表

详情

NC206190. 兰德索尔的瞭望塔

描述

兰德索尔大陆的骑士们最近遇到了一个大麻烦。

近日来，兰德索尔大陆的边境不断受到不明魔物军队的攻击，因此骑士们决定在兰德索尔大陆上修筑一些瞭望塔，以便在魔物来袭时，能够及时将消息传递到皇室和军营中。

为了简化问题，我们可以将瞭望塔的修筑过程和修筑要求，描述为如下的二维 坐标系中的问题：

兰德索尔皇室的位置位于原点 处，军营位于 轴上一点 处。骑士们在第一象限内选择了 个候选点，他们将在这 个点中，挑选若干个点修筑瞭望塔。

为了保证瞭望塔之间能够正常地项皇室和军营传递消息，任意两个瞭望塔向皇室和军营通信的信道不能够产生干扰。因此，瞭望塔的修筑选址必须符合以下要求：对于任意两个位于点 和位于点 的瞭望塔，若，则点 应该严格位于 内。（换句话说，就是 应该位于 内，且两个三角形之间只能共享 OA 这一条边。）

修筑一座瞭望塔需要耗费许多玛那（兰德索尔大陆的货币），而骑士们并不想耗费太多的预算，因此他们只想在 个候选点中，找到满足上述包含关系最多的一组点，在这些位置上修筑瞭望塔。但是兰德索尔大陆的数学和几何水平并不发达，因此骑士们希望你帮他们找到最多的一组点，使这些点符合修筑瞭望塔的条件，并告诉他们这组点的个数最大可以是多少。

输入描述

每个测试点包含多组数据，请处理到文件结束。

每组测试数据的第一行有两个整数  和，表示骑士们选定的候选点个数，以及军营所处位置 的坐标。

接下来有 行，每一行包含两个整数 x_i, y_i，表示第 个候选点的位置。

保证单个测试点的所有测试数据中，候选点的个数之和 。

保证所有的坐标数据（x_i, y_i）都在 int 的范围之内，且任意两个点不重复。

输出描述

对于每组测试数据，在单独的一行内输出一个整数，表示所给的 个点中，满足修筑包含关系的最多的一组点。

示例1

输入: 

2 4
2 1
4 2
3 4
2 2
2 3
1 3
5 4
2 1
4 2
2 2
1 2
2 3
5 5
1 1
2 2
3 3
4 4
5 5

输出: 

1
2
3
1

说明:

输入样例包含四组测试数据。

第一组测试数据如下图所示。由于两个点不严格包含（除\ OA 外有其它公共边），故每组最多只能选择在\ 1 个点上建瞭望塔，答案为 1.

第二组测试数据如下图所示。满足包含关系最多的一组点有两个，即\ B 点和\ C 点\ B, D 两点并不满足包含关系，故答案为 2.


第三组测试数据如下图所示。满足包含关系最多的一组点为\ B, C, D，故答案为 3.


第四组测试数据如下图所示。由于任意两个点都不满足严格包含的条件，故每组最多只能选择在 1 个点上建瞭望塔，答案为 1.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 315ms, 内存消耗: 13656K, 提交时间: 2020-05-18 22:03:03 

#include <bits/stdc++.h>

using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << x << endl
#else
#define debug(x)
#endif
typedef long long ll;
const int maxn = 2e5 + 5;

struct Point {
  int x, y;
  Point() : x(0), y(0) {}
  Point(int _x, int _y) : x(_x), y(_y) {}
  Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }
  void get_in() { scanf("%d%d", &x, &y); }
} P[maxn];

bool cmp_1(Point A, Point B) {
  ll tmp_1 = 1LL * A.y * B.x;
  ll tmp_2 = 1LL * A.x * B.y;
  return tmp_1 > tmp_2;
}

bool cmp_2(Point A, Point B) {
  ll tmp_1 = 1LL * A.y * B.x;
  ll tmp_2 = 1LL * A.x * B.y;
  return tmp_1 < tmp_2;
}

int N, X, mx, dp[maxn];
Point Sta[maxn], Base_A;

int find(Point A) {
  int l = 1, r = mx, res = 0;
  A = Base_A - A;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (cmp_1(A, Sta[mid]))
      res = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}

int main() {
  while (~scanf("%d%d", &N, &X)) {
    Base_A = Point(X, 0);
    for (int i = 1; i <= N; i++) P[i].get_in();
    sort(P + 1, P + N + 1, cmp_1), mx = 0;
    for (int i = 1; i <= N; i++)
    {
      Sta[dp[i] = find(P[i]) + 1] = Base_A - P[i];
      if (dp[i] > mx) mx = dp[i];
    }
    printf("%d\n", mx);
  }
  return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 248ms, 内存消耗: 2784K, 提交时间: 2020-05-17 17:32:27 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int read()
{
	int res = 0, f = 1; char c = getchar();
	while(!isdigit(c) && c != '-') c = getchar();
	if(c == '-') f = -1, c = getchar();
	while(isdigit(c)) res = (res<<3)+(res<<1)+(c^48), c = getchar();
	return res*f;
}

const double pi = acos(-1);
const int maxn = 1e5+10;
int n, X;
struct Node
{
	double x, y;
	bool operator < (const Node &u) const
	{
		return x < u.x || x == u.x && (y > u.y);
	}
} a[maxn];
double b[maxn];
int cnt;

int main()
{
	while(~scanf("%d%d", &n, &X))
	{
		for(int i = 1; i <= n; i++) 
		{
			int u = read(), v = read();
			if(X > u) a[i] = {atan(1.0*v/u), atan(1.0*v/(X-u))};
			else if(X == u) a[i] = {atan(1.0*v/u), pi/2};
			else a[i] = {atan(1.0*v/u), atan(1.0*v/(X-u))+pi};
		}
		sort(a+1, a+n+1);
		cnt = 0;
		memset(b, 0, sizeof(double)*(n+5));
		for(int i = 1; i <= n; i++)
		{
			double now = a[i].y;
			int p = lower_bound(b+1, b+cnt+1, now)-b;
			b[p] = now;
			if(p > cnt) cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}
/*
3 1
1 1
2 3
2 4

*/

上一题

© 2024 nowcoder.com