首页 > 其他分享 >asm_second 题解(坐标转换+二维偏序)

asm_second 题解(坐标转换+二维偏序)

时间:2023-05-02 13:55:47浏览次数:44  
标签:偏序 10 疑点 题解 整数 leq second dfrac

Question

Asm.Def 在第一象限内找到了n个可疑点。他需要为导弹规划路径。

image

如图所示,导弹一开始在(0,0)。它只能朝着一定的方向——即严格夹在图中两条射线间的方向(白色部分)前进。注意,它不能沿着这两条射线前进,当然也不能停在原地。

image

当导弹到达某个可疑点后,它仍然只能朝着该范围内的方向前进,如上图。

求导弹最多能经过多少个可疑点。

输入格式

第 \(1\) 行包括 \(1\) 个整数 \(n\)。
第 \(2\) 行 \(4\)个整数 \(a,b,c,d\):代表两条射线的斜率分别是 \(\dfrac{a}{b}\) 和 \(\dfrac{c}{d}\)。
接下来 \(n\) 行,每行 \(2\) 个整数 \(x_i,y_i\)(1<=xi,yi<=10^5),代表 \(i\) 号可疑点的坐标。

输出格式

一个整数,即最多能经过几个可疑点。

样例解释

image

数据范围

对于 30% 的数据,\(n \leq 1000,a=0,b=1,c=1,d=0\)。

对于 60% 的数据,\(n \leq 1000\)。

对于 100% 的数据有:

  • \(n \leq 10^5\)。

  • \(0 \leq a,b,c,d \leq 10^5\)

  • \(\dfrac{a}{b}<\dfrac{c}{d}\)(即 \(\dfrac{a}{b}\) 为靠下的那条曲线)

  • \(\dfrac{a}{b} \neq \dfrac{0}{0},\dfrac{c}{d} \neq \dfrac{0}{0}\)

  • \(1 \leq x_i,y_i \leq 10^5\)

标签:偏序,10,疑点,题解,整数,leq,second,dfrac
From: https://www.cnblogs.com/victoryang-not-found/p/17367603.html

相关文章

  • 2023湖北CCPC省赛 蒻蒟的部分题解
    题目地址C.DarknessI题意:有一个n*n的方格,最开始全是白色,如果白色周围4格有两个黑色格子,1秒后这个白色格子会变成黑色,问如果要使全部格子都变为黑色,最开始最少需要涂黑几个格子Solution对于两个黑色格子,只有当满足\[|x_1-x_2|+|y_1-y_2|≤2\]才能涂黑以这两个格子为顶点的矩......
  • 2023 Hubei Provincial Collegiate Programming Contest题解 C F H I J K M
    补题链接:https://codeforces.com/gym/104337原文链接:https://www.eriktse.com/algorithm/1136.htmlM.DifferentBilling签到题,写几个柿子然后枚举B或C即可。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ ios::sync_with_stdio(......
  • CF1477F Nezzar and Chocolate Bars 题解
    题意:有一根长为\(1\)的巧克力,已经被切了\(m-1\)刀被分成\(m\)分,接下来每次在整根长度为\(1\)的巧克力上均匀随机一个点切一刀,求每一小段巧克力长度均小于一个给定值\(K\)需要的期望次数。引理:Irwin-Hall分布:对于\(n\)个在\([0,1]\)内均匀分布的实数随机变量,它们......
  • 4 月 30 日测试题解
    4月30日测试题解T1\({\color{green}{\text{100pts}}}\text{/100pts}\)题意一个无限长宽的棋盘,给出起点\(s\)和终点\(t\),行走方式是象棋中马的走法,问最少需要走多少步。对于\(100\%\)的数据,\(|x_s|,|y_s|,|x_t|,|y_t|\le10^7\)。思路\(\text{100pts}\)首先,坐......
  • 【题解】P3338 [ZJOI2014]力
    题目描述给出\(n\)个数\(q_1,q_2,\dotsq_n\),定义\[F_j~=~\sum_{i=1}^{j-1}\frac{q_i\timesq_j}{(i-j)^2}~-~\sum_{i=j+1}^{n}\frac{q_i\timesq_j}{(i-j)^2}\]\[E_i~=~\frac{F_i}{q_i}\]对\(1\leqi\leqn\),求\(E_i\)的值。\(1\le......
  • [P5785 [SDOI2012]任务安排] 题解
    P5785[SDOI2012]任务安排题目描述分析很明显是一个dp我们不妨设\(dp[i]\)表示枚举到\(i\)的最小费用\(t[i]\)表示加工完第\(i\)个任务所用的总时间,也就是\(T[i]\)的前缀和由于每一批任务前都要一个时间为\(s\)的开机工作我们不妨把每一个这样的\(s\)秒提出来,则这\(s\)秒都......
  • CF1624G 题解
    前言题目传送门!更好的阅读体验?比较好玩的二进制题目。思路答案最小,也就是说较高位要尽可能小。所以很容易想到从最高位开始枚举。第\(i\)位为\(0\),等价于选出的所有边的第\(i\)位都为\(0\)。同时,由于我们是贪心,如果之前枚举过的第\(j\)位可以是\(0\),那么这两个条件......
  • 洛谷 P7579 「RdOI R2」称重(weigh) 题解
    题意:题目一道交互题。有n个球,里面有两个假球,假球比普通球的要轻,每次可以询问任意两组球的轻重关系,第一组轻为<,第二组轻为>,一样重量为=。思路:先考虑在一个区间内找1个假球。我们可以将区间尽量平均分为3份,先询问相等的两组球的轻重关系,分3种情况:第一组轻......
  • 【题解】CF44G Shooting Gallery
    题目大意给定\(n\)个三维空间的平面,由高度\(z\)、\(x\)的范围\([xl,xr]\)和\(y\)的范围\([yl,yr]\)来表示。有\(m\)次射击,每次射击点\((x,y)\),摧毁包含此点的\(z\)值最小的平面,输出此平面编号,若摧毁不了任何平面,输出\(0\)。题解点查平面不好做,于是可以转化为平面查点,先将平面按......
  • Codeforces Round 869 (Div.1 & Div.2) 题解
    2A.Politics因为编号为\(1\)的人一定不会离开,那么最后留下的人一定要和编号为\(1\)的人的所有参数都一致,所以计数即可。#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/hash_policy.hpp>u......