标签 凸包 下的文章

「Codeforces 1143F」U2

题目链接：Codeforces 1143F

最近 Vasya 学会了对于两个 $x$ 坐标不同的点，你可以通过他们画恰好一个类型为 $y = x ^ 2 + bx + c$ 的抛物线，其中 $b$ 和 $c$ 是实数。我们将这样的抛物线叫做 $U$ 形抛物线。

Vasya 在平面上绘制了 $n$ 个不同的点，然后对于每一对 $x$ 坐标不同的点绘制一个 $U$ 形抛物线。Vasya 想计算出有多少条抛物线满足其内部没有其他绘制的点。

我们定义 $U$ 形抛物线的内部区域是严格位于其上方的部分平面。

数据范围：$1\le n \le 10 ^ 5$，$\vert x_i\vert, \vert y_i\vert \le 10 ^ 6$。

「NOI 2007」货币兑换

题目链接：LOJ 2353

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：$A$ 纪念券（以下简称 $A$ 券）和 $B$ 纪念券（以下简称 $B$ 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $i$ 天中 $A$ 券和 $B$ 券的价值分别为 $A_i$ 和 $B_i$（元 / 单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。比例交易法分为两个方面：

• 卖出金券：顾客提供一个 $[0,100]$ 内的实数 $\text{OP}$ 作为卖出比例，其意义为：将 $\text{OP}\%$ 的 $A$ 券和 $\text{OP}\%$ 的 $B$ 券以当时的价值兑换为人民币。
• 买入金券：顾客支付 $\text{IP}$ 元人民币，交易所将会兑换给用户总价值为 $\text{IP}$ 的金券，并且，满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $i$ 天恰好为 $Rate_i$。

注意：同一天内可以进行多次操作。

小 Y 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $n$ 天内的 $A$ 券和 $B$ 券的价值 $A_i,B_i$ 以及 $Rate_i$。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $n$ 天后最多能够获得多少元钱。

数据范围：$1 \le n \le 10 ^ 5$，$0 < A_i, B_i \le 10$，$0 < Rate_i \le 100$，$0 \le \text{答案}\le 10 ^ 9$。

「Codeforces 70D」Professor's Task

题目链接：Codeforces 70D

你需要实现这样一个数据结构，维护一个点集 $S$ 的凸包。一共有 $q$ 种操作，操作分为如下 $2$ 种：

1. 将一个坐标为 $(x,y)$ 的点加入点集 $S$。点集 $S$ 的凸包可能会改变，也可能还是原来的样子。
2. 查询点 $(x,y)$ 是否在凸包内部，包括边界。

保证前 $3$ 个操作都是加入操作，且加入的 $3$ 个点构成三角形。所有加入 $S$ 的点的坐标都是不同的。

数据范围：$4\le q\le 10^5$，$-10^6\le x,y\le 10^6$。