比赛地址：http://www.acdream.net/contest.php?cid=1019
数据和标程：ACdream-9th.rar
A[二次型] B[二维极值点] C[数据结构] D[维护凸壳] E[数学推理] F[状态压缩DP]。。。

Problem A. Yet Another Conic Section Problem

Brief description:

（判定两个圆锥曲线是否全等。。所谓全等。。。是指其中一个可以经过若干次平移，旋转，反射变换变成另一个。。）

Analysis:

[二次曲线不变量]

。。本来想出成判断相似。。。但是相似不变量不太会弄。。就先判断全等。。
。似乎按照 ZJU 3488. 的做法也可以搞。。（化成标准形式。。判断曲线种类。。计算离心率（eccentricity）。。

记。。
I1 = a + c
I2 = ac - bb （二阶主子式。。
I3 = 行列式。。

K1 = A(2,2) + A(1,1) ( 其中 A(i,j) 表示去掉第 i 行第 j 列的余子式。。
那么

if ( I2 > 0 ) {
    if ( I1 , I3 同号 ） 是虚椭圆
    if ( I1 , I3 异号 ） 是椭圆
    if ( I3 == 0 ) 是一个点
}
if ( I2 < 0 ) {
    if ( I3 == 0 ) 一对相交的直线
    if ( I3 != 0 ) 双曲线
}
if ( I2 == 0 ) {
    if ( I3 != 0 ) 抛物线
    if ( I3 == 0 ) {
        if ( K1 < 0 ) 一对平行线
        if ( K1 > 0 ) 一对虚平行线
        if ( K1 == 0 ) 一对重合的直线
    }
}

。。（。。可见光是判断曲线种类。。就存在着大量的 if-else。。。）
。。相比之下。。直接利用二次曲线不变量进行比较的方法要易于操作许多。。

struct Conic{
    DB a, b, c, d, e, f;
    DB I1, I2, I3;
    void input(){
        RF(a, b, c, d, e, f);
        b/=2, d/=2, e/=2;
        I1 = a+c, I2 = a*c - sqr(b);
        I3 = a*c*f+2*b*e*d-c*d*d-a*e*e-f*b*b;
        cout << I1 << " " << I2 << " " << I3 << endl;
    }
    bool operator ==(const Conic&r) const{
        return !sgn(I1, r.I1) && !sgn(I2, r.I2) && !sgn(I3, r.I3);
    }
} C1, C2;


int main(){

#ifndef ONLINE_JUDGE
    freopen("conic03.in", "r", stdin);
    freopen("conic03.out", "w", stdout);
#endif

    Rush{
        C1.input(), C2.input();
        puts (C1 == C2 ? "Y" : "N");
    }
}

External link:

http://www.spoj.com/problems/CONIC/
[Weisstein, Eric W. “Conic Section.” From MathWorld–A Wolfram Web Resource.]
[Se 3 用系数判别二次曲线类型]
wikipedia, Matrix representation of conic sections
wikipedia, Positive-definite_matrix

Problem B. Minimization

Brief description:

… ( … 求出。。。到给定的k个点的距离的和/平方和/立方和最小的三个点。。）

Analysis:

。类似模拟退火。。。实现的过程中使用 valarray 可以极大的减少代码量。。。

.. .
		while (L > 1e-9) {
			for (int i = 0; i < k; ++i) {
				delta[i] = ps[i] - who;
				mod[i] = dist(delta[i]);
			}
			double smod = accumulate(mod.begin(), mod.end(), 0.0);
			for (int i = 0; i < k; ++i) {
				delta[i] *= pow(mod[i] / smod, d - 1);
			}
			point v = accumulate(delta.begin(), delta.end(), point(0.0, n));
			v *= L;
			double t = tryIt(ps, who + v, d + 1);
			if (t < ans) {
				ans = t;
				who += v;
			} else {
				L /= 2;
			}
		}
.. .

Problem C. Crayon

Brief description:

。。动态维护一组区间，支持插入删除。。询问与某个区间至少有一个公共点的区间数。。）。。

Analysis:

.基本上就是校赛我脑残没做出来的那题。。 其实就是计数补集。。。。很典型的正难则反。。。。

External link:

http://www.spoj.com/problems/CRAYON/

Problem D. Vision Field

Brief description:

。。。x 轴正半轴上分布着 n 个楼房 (i, Ai)。。问站在 (0, h) 往右可以看到多少楼房。。）

Analysis:

设一开始视点处在无穷高位置。。那么显然所有楼都能看到。。
。。随着视点的下降。。一些建筑开始被遮盖。。

如果我们能够预处理出每个建筑被遮盖的时间。。
那么就可以 O(logn) 时间内在线的回答每个询问。（二分。。

现在考虑如何预处理每个建筑被遮盖的时间。。
朴素方法是对每个建筑和他前面的建筑的顶端连线与 y 轴交点。
。就是其被遮盖的时间。。
这个 O(n2) 的做法显然弱爆。。

考察相邻的建筑
可以证明。。最早被遮盖的建筑一定是从某组相邻的建筑中产生的。。
（类似 Ural 1010 。。

我们用优先队列维护当前所有未被遮盖的建筑。
。。则其关键字为于其左边第一个未被遮盖的建筑的顶端。。
。所形成的连线与 y 轴交点。。

复杂度 O(nlogn)。
总的复杂度为 O((n+m)logn)
。。（。。更好的方法是维护凸壳。。。预处理的复杂度 O(n + nlogn) （排序。。

External link:

http://www.spoj.com/problems/VISION/

Problem E. Evil Pu*&le

。。。puts(“0”);

Problem F. Madotsuki‘s Pattern

Brief description:

.. 求最多可以构造多少 “窗子花纹” 和，以及有多少可以得到这个最优解的方案数。。。）

Analysis:

状态压缩 DP。。本来想出成可以可以考虑巨大窗子花纹的。。
比如一个 2阶窗子。。就是

110011
110011
001100
001100

（得分大概需要成指数增长。。优先构造大型的花纹。。。但是发现不太会弄。。就先考虑 1 阶的出出来了。o(≧v≦)o~~。。。）

External link:

http://www.spoj.com/problems/MDT1/

Posted by xiaodao
Category: ACdream