微网站的制作过程,wordpress必须安装php,中国网站排名100,免费申请域名注册problem
luogu-P3340
题面写得那么长#xff0c;其实说白了就是求一条直线#xff0c;使得若干个点到这条直线的距离平方的和最小#xff0c;求这个最小值。
solution
我超爱数学#xff0c;数学就是我的命#xff0c;我一天不学数学我就难受#xff01;
假设拟合出…problem
luogu-P3340
题面写得那么长其实说白了就是求一条直线使得若干个点到这条直线的距离平方的和最小求这个最小值。
solution
我超爱数学数学就是我的命我一天不学数学我就难受
假设拟合出的直线为ykxbykxbykxb。
点到直线 Ax0By0C0Ax_0By_0C0Ax0By0C0 的距离公式d∣AxByC∣A2B2d\frac{|AxByC|}{\sqrt{A^2B^2}}dA2B2∣AxByC∣ 不会就去问数学老师
接下来就是推式子 ∑(kxi−yib)2k21∑k2xi2yi2b2−2kxiyi2kbxi−2byik21\frac{\sum(kx_i-y_ib)^2}{k^21}\frac{\sum k^2x_i^2y_i^2b^2-2kx_iy_i2kbx_i-2by_i}{k^21} k21∑(kxi−yib)2k21∑k2xi2yi2b2−2kxiyi2kbxi−2byi xi,yix_i,y_ixi,yi 都可被视作已知量所以只有 k,bk,bk,b 是未知数。
答案要最小化这个式子的值k,bk,bk,b 没有任何等量关系所以我们两个各自最小化即可。
先最小化 bbb 的求值把 kkk 假想成已知量。 ∑(b2(2kxi−2yi)byi2−2kxiyik2xi2)k21nb2∑(2kxi−2yi)b∑(yi2−2kxiyik2xi2)k21\frac{\sum(b^2(2kx_i-2y_i)by_i^2-2kx_iy_ik^2x_i^2)}{k^21}\frac{nb^2\sum(2kx_i-2y_i)b\sum(y_i^2-2kx_iy_ik^2x_i^2)}{k^21} k21∑(b2(2kxi−2yi)byi2−2kxiyik2xi2)k21nb2∑(2kxi−2yi)b∑(yi2−2kxiyik2xi2) 显然这是个关于 bbb 的二次函数。根据数学知识我们知道当 b∑(2yi−2kxi)2nb\frac{\sum(2y_i-2kx_i)}{2n}b2n∑(2yi−2kxi) 时取到最低点。
且 b∑(2yi−2kxi)2n∑yi−k∑xinb\frac{\sum(2y_i-2kx_i)}{2n}\frac{\sum y_i-k\sum x_i}{n}b2n∑(2yi−2kxi)n∑yi−k∑xi恰好发现 ∑xinxˉ\frac{\sum x_i}{n}\bar{x}n∑xixˉ平均数∑yinyˉ\frac{\sum y_i}{n}\bar{y}n∑yiyˉ。
然后现在把 bbb 当作常量 byˉ−kxˉb\bar{y}-k\bar{x}byˉ−kxˉ把 kkk 当作未知数。 n(yˉ−kxˉ)2∑(2kxi−2yi)(yˉ−kxˉ)∑(yi2−2kxiyik2xi2)k21\frac{n(\bar{y}-k\bar{x})^2\sum(2kx_i-2y_i)(\bar{y}-k\bar{x})\sum(y_i^2-2kx_iy_ik^2x_i^2)}{k^21} k21n(yˉ−kxˉ)2∑(2kxi−2yi)(yˉ−kxˉ)∑(yi2−2kxiyik2xi2)
nyˉ2−2nkxˉyˉnk2xˉ2∑(2kxiyˉ−2yiyˉ−2k2xixˉ2yikxˉ)∑(yi2−2kxiyik2xi2)k21\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_ik^2x_i^2)}{k^21} k21nyˉ2−2nkxˉyˉnk2xˉ2∑(2kxiyˉ−2yiyˉ−2k2xixˉ2yikxˉ)∑(yi2−2kxiyik2xi2)
∑(xˉ2−2xixˉxi2)k2∑(−2xˉyˉ2xiyˉ2yixˉ−2xiyi)k∑(yˉ2−2yiyˉyi2)k21\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^21} k21∑(xˉ2−2xixˉxi2)k2∑(−2xˉyˉ2xiyˉ2yixˉ−2xiyi)k∑(yˉ2−2yiyˉyi2)
为了式子的简洁美观我们记 {A∑xˉ2−∑2xix∑xi2B−2nxˉyˉ∑2xiyˉ∑2yixˉ−∑2xiyiCnyˉ2−∑2yiyˉ∑yi2\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\\ Cn\bar{y}^2-\sum2y_i\bar{y}\sum y_i^2 \end{cases} ⎩⎪⎨⎪⎧A∑xˉ2−∑2xix∑xi2B−2nxˉyˉ∑2xiyˉ∑2yixˉ−∑2xiyiCnyˉ2−∑2yiyˉ∑yi2 则有 Ak2BkCk21→ans\frac{Ak^2BkC}{k^21}\rightarrow ansk21Ak2BkC→ans。 ansAk2BkCk21⇒ans(k21)Ak2BkC⇒(A−ans)k2BkC−ans0ans\frac{Ak^2BkC}{k^21}\Rightarrow ans(k^21)Ak^2BkC\Rightarrow (A-ans)k^2BkC-ans0 ansk21Ak2BkC⇒ans(k21)Ak2BkC⇒(A−ans)k2BkC−ans0 因为题目肯定是有解的所以这个二元一次方程要有根即 Δ≥0\Delta\ge 0Δ≥0。 KaTeX parse error: Undefined control sequence: \ at position 75: …nsB^2-4AC\ge 0\̲ ̲ 又得到了一个关于 ansansans 的开口向下的二次函数ansansans 最小取值就是其方程的较小根再用一次求根公式即可。
所以我们只需要维护 n,∑xi,∑yi,∑xi2,∑yi2,∑xiyin,\sum x_i,\sum y_i,\sum x_i^2,\sum y_i^2,\sum x_iy_in,∑xi,∑yi,∑xi2,∑yi2,∑xiyi 这几个信息。
一条路径上的信息维护发现树上差分即可做到记从根到该点一路上的信息之和。
基环树存一下环的点然后把环拍成链考虑有两种走环的方式比较最小值即可。
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;
}
