problem
luogu-P3340
题面写得那么长，其实说白了就是求一条直线，使得若干个点到这条直线的距离平方的和最小，求这个最小值。
solution
我超爱数学，数学就是我的命，我一天不学数学我就难受！
假设拟合出的直线为：
y
=
k
x
+
b
y=kx+b
y=kx+b。
点到直线
A
x
0
+
B
y
0
+
C
=
0
Ax_0+By_0+C=0
Ax0?+By0?+C=0 的距离公式：
d
=
∣
A
x
+
B
y
+
C
∣
A
2
+
B
2
d=\frac{|Ax+By+C|}{\sqrt{A^2+B^2}}
d=A2+B2
?∣Ax+By+C∣? 不会就去问数学老师
接下来就是推式子：
∑
(
k
x
i
?
y
i
+
b
)
2
k
2
+
1
=
∑
k
2
x
i
2
+
y
i
2
+
b
2
?
2
k
x
i
y
i
+
2
k
b
x
i
?
2
b
y
i
k
2
+
1
\frac{\sum(kx_i-y_i+b)^2}{k^2+1}=\frac{\sum k^2x_i^2+y_i^2+b^2-2kx_iy_i+2kbx_i-2by_i}{k^2+1}
k2+1∑(kxi??yi?+b)2?=k2+1∑k2xi2?+yi2?+b2?2kxi?yi?+2kbxi??2byi??
x
i
,
y
i
x_i,y_i
xi?,yi? 都可被视作已知量，所以只有
k
,
b
k,b
k,b 是未知数。
答案要最小化这个式子的值，
k
,
b
k,b
k,b 没有任何等量关系，所以我们两个各自最小化即可。
先最小化
b
b
b 的求值，把
k
k
k 假想成已知量。
=
∑
(
b
2
+
(
2
k
x
i
?
2
y
i
)
b
+
y
i
2
?
2
k
x
i
y
i
+
k
2
x
i
2
)
k
2
+
1
=
n
b
2
+
∑
(
2
k
x
i
?
2
y
i
)
b
+
∑
(
y
i
2
?
2
k
x
i
y
i
+
k
2
x
i
2
)
k
2
+
1
=\frac{\sum(b^2+(2kx_i-2y_i)b+y_i^2-2kx_iy_i+k^2x_i^2)}{k^2+1}=\frac{nb^2+\sum(2kx_i-2y_i)b+\sum(y_i^2-2kx_iy_i+k^2x_i^2)}{k^2+1}
=k2+1∑(b2+(2kxi??2yi?)b+yi2??2kxi?yi?+k2xi2?)?=k2+1nb2+∑(2kxi??2yi?)b+∑(yi2??2kxi?yi?+k2xi2?)?
显然这是个关于
b
b
b 的二次函数。根据数学知识，我们知道当
b
=
∑
(
2
y
i
?
2
k
x
i
)
2
n
b=\frac{\sum(2y_i-2kx_i)}{2n}
b=2n∑(2yi??2kxi?)? 时取到最低点。
且
b
=
∑
(
2
y
i
?
2
k
x
i
)
2
n
=
∑
y
i
?
k
∑
x
i
n
b=\frac{\sum(2y_i-2kx_i)}{2n}=\frac{\sum y_i-k\sum x_i}{n}
b=2n∑(2yi??2kxi?)?=n∑yi??k∑xi??，恰好发现
∑
x
i
n
=
x
ˉ
\frac{\sum x_i}{n}=\bar{x}
n∑xi??=xˉ（平均数），
∑
y
i
n
=
y
ˉ
\frac{\sum y_i}{n}=\bar{y}
n∑yi??=yˉ?。
然后现在把
b
b
b 当作常量
b
=
y
ˉ
?
k
x
ˉ
b=\bar{y}-k\bar{x}
b=yˉ??kxˉ，把
k
k
k 当作未知数。
=
n
(
y
ˉ
?
k
x
ˉ
)
2
+
∑
(
2
k
x
i
?
2
y
i
)
(
y
ˉ
?
k
x
ˉ
)
+
∑
(
y
i
2
?
2
k
x
i
y
i
+
k
2
x
i
2
)
k
2
+
1
=\frac{n(\bar{y}-k\bar{x})^2+\sum(2kx_i-2y_i)(\bar{y}-k\bar{x})+\sum(y_i^2-2kx_iy_i+k^2x_i^2)}{k^2+1}
=k2+1n(yˉ??kxˉ)2+∑(2kxi??2yi?)(yˉ??kxˉ)+∑(yi2??2kxi?yi?+k2xi2?)?
=
n
y
ˉ
2
?
2
n
k
x
ˉ
y
ˉ
+
n
k
2
x
ˉ
2
+
∑
(
2
k
x
i
y
ˉ
?
2
y
i
y
ˉ
?
2
k
2
x
i
x
ˉ
+
2
y
i
k
x
ˉ
)
+
∑
(
y
i
2
?
2
k
x
i
y
i
+
k
2
x
i
2
)
k
2
+
1
=\frac{n\bar{y}^2-2nk\bar{x}\bar{y}+nk^2\bar{x}^2+\sum(2kx_i\bar{y}-2y_i\bar{y}-2k^2x_i\bar{x}+2y_ik\bar{x})+\sum(y_i^2-2kx_iy_i+k^2x_i^2)}{k^2+1}
=k2+1nyˉ?2?2nkxˉyˉ?+nk2xˉ2+∑(2kxi?yˉ??2yi?yˉ??2k2xi?xˉ+2yi?kxˉ)+∑(yi2??2kxi?yi?+k2xi2?)?
=
∑
(
x
ˉ
2
?
2
x
i
x
ˉ
+
x
i
2
)
k
2
+
∑
(
?
2
x
ˉ
y
ˉ
+
2
x
i
y
ˉ
+
2
y
i
x
ˉ
?
2
x
i
y
i
)
k
+
∑
(
y
ˉ
2
?
2
y
i
y
ˉ
+
y
i
2
)
k
2
+
1
=\frac{\sum(\bar{x}^2-2x_i\bar{x}+x_i^2)k^2+\sum(-2\bar{x}\bar{y}+2x_i\bar{y}+2y_i\bar{x}-2x_iy_i)k+\sum(\bar{y}^2-2y_i\bar{y}+y_i^2)}{k^2+1}
=k2+1∑(xˉ2?2xi?xˉ+xi2?)k2+∑(?2xˉyˉ?+2xi?yˉ?+2yi?xˉ?2xi?yi?)k+∑(yˉ?2?2yi?yˉ?+yi2?)?
为了式子的简洁美观，我们记：
{
A
=
∑
x
ˉ
2
?
∑
2
x
i
x
+
∑
x
i
2
B
=
?
2
n
x
ˉ
y
ˉ
+
∑
2
x
i
y
ˉ
+
∑
2
y
i
x
ˉ
?
∑
2
x
i
y
i
C
=
n
y
ˉ
2
?
∑
2
y
i
y
ˉ
+
∑
y
i
2
\begin{cases} A=\sum\bar{x}^2-\sum 2x_ix+\sum x_i^2\\ B=-2n\bar{x}\bar{y}+\sum 2x_i\bar{y}+\sum2y_i\bar{x}-\sum2x_iy_i\\ C=n\bar{y}^2-\sum2y_i\bar{y}+\sum y_i^2 \end{cases}
??????A=∑xˉ2?∑2xi?x+∑xi2?B=?2nxˉyˉ?+∑2xi?yˉ?+∑2yi?xˉ?∑2xi?yi?C=nyˉ?2?∑2yi?yˉ?+∑yi2??
则有
A
k
2
+
B
k
+
C
k
2
+
1
→
a
n
s
\frac{Ak^2+Bk+C}{k^2+1}\rightarrow ans
k2+1Ak2+Bk+C?→ans。
a
n
s
=
A
k
2
+
B
k
+
C
k
2
+
1
?
a
n
s
(
k
2
+
1
)
=
A
k
2
+
B
k
+
C
?
(
A
?
a
n
s
)
k
2
+
B
k
+
C
?
a
n
s
=
0
ans=\frac{Ak^2+Bk+C}{k^2+1}\Rightarrow ans(k^2+1)=Ak^2+Bk+C\Rightarrow (A-ans)k^2+Bk+C-ans=0
ans=k2+1Ak2+Bk+C??ans(k2+1)=Ak2+Bk+C?(A?ans)k2+Bk+C?ans=0
因为题目肯定是有解的，所以这个二元一次方程要有根，即
Δ
≥
0
\Delta\ge 0
Δ≥0。
KaTeX parse error: Undefined control sequence: \ at position 75: …ns+B^2-4AC\ge 0\? ?
又得到了一个关于
a
n
s
ans
ans 的开口向下的二次函数，
a
n
s
ans
ans 最小取值就是其方程的较小根，再用一次求根公式即可。
所以我们只需要维护
n
,
∑
x
i
,
∑
y
i
,
∑
x
i
2
,
∑
y
i
2
,
∑
x
i
y
i
n,\sum x_i,\sum y_i,\sum x_i^2,\sum y_i^2,\sum x_iy_i
n,∑xi?,∑yi?,∑xi2?,∑yi2?,∑xi?yi? 这几个信息。
一条路径上的信息维护，发现树上差分即可做到，记从根到该点一路上的信息之和。
基环树存一下环的点，然后把环拍成链，考虑有两种走环的方式，比较最小值即可。
code
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
struct node {
int n, sumx, sumy, sumx2, sumy2, sumxy;
void insert( int x, int y ) { n ++, sumx += x, sumy += y, sumx2 += x * x, sumy2 += y * y, sumxy += x * y; }
double calc() {
double var_x = sumx * 1.0 / n, var_y = sumy * 1.0 / n;
double A = sumx2 - 2 * var_x * sumx + n * var_x * var_x;
double B = - 2 * sumxy + 2 * sumx * var_y + 2 * sumy * var_x - 2 * n * var_x * var_y;
double C = sumy2 - 2 * sumy * var_y + n * var_y * var_y;
double a = 4, b = - 4 * ( A + C ), c = 4 * A * C - B * B;
double delta = sqrt( b * b - 4 * a * c );
return ( - b - delta ) / ( 2 * a );
}
}f[maxn], g[maxn];
node operator + ( node HM, node NB ) { HM.n += NB.n, HM.sumx += NB.sumx, HM.sumy += NB.sumy, HM.sumx2 += NB.sumx2, HM.sumy2 += NB.sumy2, HM.sumxy += NB.sumxy; return HM; }
node operator - ( node HM, node NB ) { HM.n -= NB.n, HM.sumx -= NB.sumx, HM.sumy -= NB.sumy, HM.sumx2 -= NB.sumx2, HM.sumy2 -= NB.sumy2, HM.sumxy -= NB.sumxy; return HM; }
struct point { int x, y; }p[maxn];
int n, m, Q, cnt;
int fa[maxn], dep[maxn], top[maxn], root[maxn], vis[maxn], siz[maxn], son[maxn], num[maxn], circle[maxn];
vector < int > G[maxn];
int lca( int u, int v ) {
while( top[u] ^ top[v] )
if( dep[top[u]] < dep[top[v]] ) v = fa[top[v]];
else u = fa[top[u]];
return dep[u] < dep[v] ? u : v;
}
void dfs1( int u, int rt ) {
root[u] = rt, siz[u] = vis[u] = 1, son[u] = 0;
f[u] = f[fa[u]], f[u].insert( p[u].x, p[u].y );
for( int v : G[u] )
if( ! vis[v] and v ^ fa[u] ) {
fa[v] = u;
dep[v] = dep[u] + 1;
dfs1( v, rt );
siz[u] += siz[v];
if( siz[son[u]] < siz[v] ) son[u] = v;
}
}
void dfs2( int u, int t ) {
top[u] = t;
if( son[u] ) dfs2( son[u], t );
else return;
for( int v : G[u] )
if( fa[v] == u and son[u] ^ v ) dfs2( v, v );
}
void work() {
for( int u = 1;u <= n;u ++ )
for( int v : G[u] )
if( fa[v] ^ u and fa[u] ^ v ) {
if( dep[u] > dep[v] ) swap( u, v );
while( v ^ u ) {
circle[++ cnt] = v;
num[v] = cnt;
g[cnt] = g[cnt - 1];
g[cnt].insert( p[v].x, p[v].y );
vis[v] = 1;
v = fa[v];
}
circle[++ cnt] = u;
num[u] = cnt;
g[cnt] = g[cnt - 1];
g[cnt].insert( p[u].x, p[u].y );
vis[u] = 1;
return;
}
}
int main() {
scanf( "%d %d", &n, &m );
for( int i = 1;i <= n;i ++ ) scanf( "%d %d", &p[i].x, &p[i].y );
for( int i = 1, u, v;i <= m;i ++ ) {
scanf( "%d %d", &u, &v );
G[u].push_back( v );
G[v].push_back( u );
}
dfs1( 1, 1 );
memset( vis, 0, sizeof( vis ) );
if( n == m ) work();
else circle[cnt = 1] = 1;
memset( fa, 0, sizeof( fa ) );
for( int i = 1;i <= cnt;i ++ ) dfs1( circle[i], circle[i] ), dfs2( circle[i], circle[i] );
scanf( "%d", &Q );
while( Q -- ) {
int x, y;
scanf( "%d %d", &x, &y );
if( root[x] == root[y] )
printf( "%.5f\n", (f[x] + f[y] - f[lca( x, y )] - f[fa[lca( x, y )]] ).calc() );
else {
if( num[root[x]] > num[root[y]] ) swap( x, y );
node u = f[x] - f[root[x]] + f[y] - f[root[y]] + g[num[root[y]]] - g[num[root[x]] - 1];
node v = f[x] - f[root[x]] + f[y] - f[root[y]] + g[num[root[x]]] + g[cnt] - g[num[root[y]] - 1];
printf( "%.5f\n", min( u.calc(), v.calc() ) );
}
}
return 0;
}
|