比赛地址：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~~。。。）
