[CF1030D] Vasya and Triangle

Vasya and Triangle

翻译:

Vasya有三个数n,m,k。他想要找到三个整点(x1,y1),(x2,y2),(x3,y3)满足0≤x1,x2,x3≤n,0≤y1,y2,y3≤m并且由这三点组成的三角形面积等于nm/k。

帮助Vasya找到这样的点(如果可能的话)。如果有多组解,输出任意一组即可。

Input

仅一行,包括三个整数n,m,k(1≤n,m≤10^9,2≤k≤10^9)。

Output

如果没有这样的点,输出"NO"。

否则在第一行输出"YES"。接下来三行每行包括两个整数xi,yi,代表点的坐标。如果有多组解,输出任意一组即可。

你可以任意输出大写或小写的英文字母。

Note

在第一组样例中三角形的面积等于nm/k=4。这个三角形的图示在下方。

在第二组样例中不存在三角形的面积满足nm/k=16/7。

Tutorial

将任意坐标都是整点的三角形面积加倍总会得到一个整数。这就是如果2nm不能被k整除,就没有合法的三角形的原因。

反之,总是存在满足条件的三角形。我们将会在接下来的算法里构造答案。首先,如果k是偶数那么就将它除2。接着,令g = gcd(k, n),在这里gcd(x, y)代表x和y的最大公约数。取k' = k / g,令 a = n / g 并使其作为三角形的一边长。然后令b = m / k'作为三角形的另一边长。现在,如果k是奇数我们应将其中一边长乘以2。如果a < n那么令a = 2a,否则就令b = 2b。b不会大于m,因为假如a=n那么b是严格小于m的。

答案就是由顶点(0, 0), (a, 0), (0, b)构成的三角形。你可以检查它的面积是否等于nm/k。

继续阅读[CF1030D] Vasya and Triangle

BZOJ【1007】水平可见直线

题意

给出n条直线,求从上到下能看到直线的编号。

分析

对于每两条直线,都有一条直线被另一条直线遮住一部分。

设两条直线Y1= k1X + b1, Y2 = k2X + b2(K1 < K2)。

以及第三条直线Y3 = k3X + b3;

可以算出前两条直线的交点的横坐标为X = (b2-b1)/(k1 - k2)

由于k2 > k1,所以当x<X时,Y1遮住Y2,当x>X时,Y2遮住Y1。

而第三条直线分别和Y1,Y2的交点横坐标为X' = (b3 - b1) / (k1 - k3), X'' = (b3 - b1) / (k1 - k3)

同理,由于k3 > k1,所以当x<X'时,Y1遮住Y3,当x>X'时,Y3遮住Y1。

由于k3 > k2,所以当x<X''时,Y2遮住Y3,当x>X''时,Y3遮住Y2。

所以当X''<X'时,X''<X'<X,则x<X部分Y2被Y1遮住,x>''部分Y2被Y3遮住。于是Y2被完全遮住。

于是就将直线按k从小到大排序,对于每一条直线判断其能否遮住前一条。

继续阅读BZOJ【1007】水平可见直线

[BZOJ 2300] [HAOI 2011] 防线修建

题意:只有删点与查询操作,动态地维护一个上凸包的周长。

首先可以把题目离线化,倒转时间轴,则可以把题目转换成动态加点并维护凸包周长。

维护的实现可以采用平衡树(set)来做:在树上找到当前点的前驱与后继点(按 xy 坐标排序),然后判断是否符合凸包条件,若不满足则不断删去前驱后继并更新周长。

Note:

  1. 计算初始答案前就应当构建出一个凸包(可以用后面的方法做)。
  2. 这题 cin / cout 非常慢,全改成 scanf / printf 后快了 1s+

Reference:

https://erjiaqing.github.io/2014/04/14/bzoj2300/

代码如下:

继续阅读[BZOJ 2300] [HAOI 2011] 防线修建

BZOJ【2300】防线修建

描述

在第一象限中给出m个点,其中一共有3个点一定要保护,求最小凸包周长。

在这题中,河道相等于一条防线,于是题目就简化成了求最小上凸包。再看看数据,每次减掉一个要保护的点。我们可以从后往前看,先把没有被询问到的点做一次凸包,接着就可以把删除的点看做是加上去的点。比如把2 3 1 4点依次删除询问,可以看做刚开始一个点都没有,接着把4 1 3 2点依次加入。

所以我们只要先存心每次询问,从后往前做动态凸包即可。

至于动态凸包,由于有三个点一定要保护,于是对于每个新加入的点,找出与其相邻的点, 用叉积判断其是否最优,若不是,就可以将其两边的点删除,继续判断。

在这里,找于加入的点相邻的点可以用平衡树来维护,每次需要O(logn)的时间查找。

可以用自带的set来实现。

关于set,可以看这http://blog.csdn.net/sunshinewave/article/details/8068326

继续阅读BZOJ【2300】防线修建

BZOJ1913 [APIO2010] 信号覆盖 signaling

BZOJ1913

题意:

给出平面上n个点,在这N个点中选3点构成一个圆,求圆上或圆内总点数的期望值。n 1500,保证无特殊情况。

题解:

显然一共有种情况,暴力枚举不可取。

考虑任取四个点构成一个四边形,可能有凸四边形和凹四边形两种情况。显然在一个四边形上任取三个点,有4种情况,每种情况都至少有3个点在圆上(即构成圆的3点),因此可以在计算时忽略这3个点,在输出时+3即可。由几何知识可得,在一个凸四边形上任取三个点,剩余的那个点在圆内可能有2种情况,而对于一个凹四边形可能有1种情况,那么要求的就变成了统计两种四边形的数目。

因为一共有个四边形,所以我们可以统计凸四边形的个数。首先枚举一个点,以这个点为原点,将其余点以极角序排序,然后使用类似旋转卡壳的思想,枚举另外两个点,保持这两个点的极角差<π,统计两点之间的点数即可。

时间复杂度为

[BZOJ 2338] [HNOI 2011] 数矩形

本题两个关键点:

1. 找到四个能构成矩形的点

这一步有一个巧妙的做法:因对角线长度相等且互相平分的四边形为矩形,故可以将给定的点两两连为线段——若两条线段长度相等且中点相同,则这两条线段的四个顶点能构成一个矩形

2. 计算过程中保持精度

可以发现,在计算过程中可能导致精度损失的地方只有计算线段长度时的 sqrt() 与计算中点时的 / 2. 。这个好办——因为只需要长度与中点位置的相对值,所以存长度时不需要开方,中点坐标也不需要除以 2 了。

具体实现过程只需要对各条线段按长度与中点进行排序(保证长度中点均相同的线段落在连续区间),对每条线段向前枚举其他所有长度中点均相同的线段(并不会超时......),用叉积计算面积更新答案即可。

Reference:

http://blog.csdn.net/PoPoQQQ/article/details/39995729

代码如下:

继续阅读[BZOJ 2338] [HNOI 2011] 数矩形

BZOJ【2338】画矩形

这题要求找出一个最大面积的矩形,学过数学的都知道:矩形对角线交于一点,而且两条对角线相等。于是我们就可以枚举每一条线段,按长度排序,取长度相等的判断他们的中点是否重合,重合的话就可以构成一个矩形。

按照上面的方法,枚举线段要n^2, 排序要n^2log(n^2),所以时间大概为O(n^2log(n^2))。

但是这题的数据有10^8,如果用两点之间距离公式和中点公式有可能被卡精度,于是可以在求距离是不开根号,直接用long long存,中点公式也不除2,这样可以避免精度的影响。

最后,在求面积时用叉积求即可。