首页 > 其他分享 >ABC292F题解

ABC292F题解

时间:2023-03-09 15:14:25浏览次数:60  
标签:倾斜角 atan 题解 坐标 theta ABC292F

首先先钦定\(a\le b\),否则交换一下就行。

方法1:二分答案。

容易发现,答案至少为\(a\),并且用左下角为一个顶点一定不会更劣,并且另外两个点一定都在线段上(否则可以调整)。我们就枚举另外两个的一个,就可以得到另一个点的坐标:用勾股定理求出长度,再用atan算出倾斜角,另一个线段的倾斜角就是\(120-atan(L/mid)\),可以得到坐标,如果在矩形内则合法。

方法2:O(1)求解

我们可以把第一个的倾斜角直接设出来\(\theta\),则有一个的坐标是\((A,A tan\theta)\),另一个的坐标我们可以求解出来,而点在矩形里的条件,就是y坐标>=0,x坐标<=B,据此我们可以解出一个关于\(tan\theta\)的不等式组,我们需要\(\theta\)越大越好,这样就可以O(1)求出答案。

具体结论推导也很容易但是latex不太好打,直接放图吧:

image

Submission:
二分:https://atcoder.jp/contests/abc292/submissions/39551499

标签:倾斜角,atan,题解,坐标,theta,ABC292F
From: https://www.cnblogs.com/IceYukino/p/17198452.html

相关文章

  • CF207C3 Game with Two Trees 题解
    脑子不够,科技来凑。不过好像也没有用多么高级的科技……首先这个题目很坏,它让你翻转\(S_{t_2}\)。即从\(t_2\)某个节点往下走到另一个节点的路径所表示的字符串。这个......
  • Python自动化登录验证码问题解决
     1.测试环境中通常解决验证码问题的方法 在测试环境中我们通常通过各种手段来逃避或者获得验证,而这些手段主要是要求开发者在开发的时候留有一定的后门。下面简述几种......
  • 【题解】ARC157 A-D
    因为有的题代码没写出来,所以代码就先咕咕咕了。A.XXYYX题目分析:可以发现每一个XY必然伴随着出现一次YX,当然可能会有一个XY没有伴随的YX的。而且若必须存在XX......
  • 【题解】[Ynoi2015] 我回来了
    题目分析:所谓的期望乘以\(R-L+1\)其实就是求亵渎的触发次数,因为我们能选择的伤害只有\(R-L+1\)种。有一个很显然的转化,就是对于伤害\(d\),我们以随从的血量......
  • DP练习1题解
    这是2023.3.7DP题单十个题的题解。T1ColoredSubgraphs(CF1796E)简要题意:给定一棵树,你要对树进行链剖分,必须剖成上下竖直的链,求剖后最短链的长度最大值。最小值最大......
  • 【题解】[Ynoi2013] 大学
    题目分析:考虑对于一次修改至少会让\(x\)变成\(\frac{x}{2}\)所以对于每一个数最多被操作\(\log{n}\)次,那么直接暴力操作就好了。所以其实关键问题是每次怎么找到哪......
  • QOJ5256 [CERC2022] H. Insertions 题解
    题面题意:给定字符串\(S,T,P\),求将\(T\)插入进\(S\)之后\(P\)最多的出现次数。输出:最多的出现次数;达到这个最多出现次数的插入位置数量;达到这个最多出现次数......
  • 【题解】[Ynoi2010] y-fast trie
    题目分析:显然可以对于所有的\(x\)对\(C\)取模后处理。那么就是两种情况:\(x+y\geC\)\(x+y<C\)对于第一种情况直接找最大的两个数就好了,关键就是第二种情......
  • 春测2023 T2题解
    这是一个从暴力到正解的过程。暴力从\(1\)枚举到\(\sqrtn\),枚举每一个\(x\),进行累乘,顺便用一个map数组判重,时间复杂度\(\mathcal{O}(\sqrtn\logn\logn)\),直接T飞......
  • Ubuntu服务器ssh缓慢问题解决
    Ubuntu服务器ssh缓慢问题解决现象:ssh登陆或su-账号时间较长 排查:1、查看了/var/log/syslog未发现明显报错2、查看/var/log/auth.log发现有pam_systemd:Failedtocreate......