夜空与花海 (flower)
直接输出第二个样例即可获得 。
让我们来正经地看看一下这道题。不难看出，对边的描述实际上就是在描述向量，边 实际上就是向量 。所以整个多边形就是若干向量首尾相连形成的闭合图形（小性质：）。
对于第 条边，他会选择第 条边的终点 向第 条边做垂线，垂足为 。
有了刚刚对向量的理解，我们可以发现， 就是向量 在向量 上的投影。旋转 之后，
发现变成了向量 的投影和向量 的模长之积。考虑一下，这两个向量模长乘积的几何意义是什么？
显然，向量 的投影和向量 的模长之积就是向量 和向量 的点积（数量积）。
点积：
几何表示：；
坐标表示：。
所以：
就很好搞了。
现在我们已经完成了计算 的问题，现在考虑如何修改。
现在考虑向量 延长 个单位怎么做。先给结论：
其中 表示延长 个单位。
证明：
还是从几何意义考虑，如下图：
很显然 ，那么 ，所以 ，进一步得到 。
即：。
所以新的向量：
好的，现在我们知道了第 个向量，但是同时第 个向量也是会更改的，那么第 个向量应该变成什么呢？
我们还是从图上考虑。如图， 是原来的向量 ， 是更改后的向量 ， 是原来的向量 ， 是更改后的向量 。
根据基本的向量加减法，可以得到：
用坐标表示出来：
现在修改操作也完成了。
那么对于 ，直接暴力维护每个向量的 ，求和的时候暴力计算 即可。有时候 可能是负数，但是我们知道我们只要知道修改的量，所以要取绝对值。
由于 的下一条边是 ，所以需要特判一下。注意用 double。
pair<double, double> vec[MAXN];
double abc(double a, double b)
{
return sqrt(a * a + b * b);
}
signed main()
{
vec[n + 1] = vec[1];
while(m--)
{
int opt, l, r;
scanf("%lld%lld%lld", &opt, &l, &r);
if(opt == 1)
{
double ans = 0.00;
for(int i = l; i <= r; i++)
{
ans += abs(vec[i + 1].fi * vec[i].fi + vec[i + 1].se * vec[i].se);
}
printf("%.6lf\n", ans / 2.00);
}
else
{
np ver1 = mp((abc(vec[l].fi, vec[l].se) + r) / abc(vec[l].fi, vec[l].se) * vec[l].fi, (abc(vec[l].fi, vec[l].se) + r) / abc(vec[l].fi, vec[l].se) * vec[l].se);
np ver2 = mp(vec[l].fi + vec[l + 1].fi, vec[l].se + vec[l + 1].se);
np ver3 = mp(ver2.fi - ver1.fi, ver2.se - ver1.se);
if(l == 1) vec[n + 1] = ver1;
if(l == n) vec[1] = ver3;
vec[l] = ver1;
vec[l + 1] = ver3;
}
}
return 0;
}
当然，我们也可以直接封装向量。以下代码来自庞队：
struct V{
double x,y,len;
V(){}
V(double _x,double _y){
x = _x,y = _y;
len = sqrt(x * x + y * y);
}
void get_len(){
len = sqrt(x * x + y * y);
}
}a[N];
V operator + (V a,V b){return V(a.x + b.x,a.y + b.y);}
V operator - (V a,V b){return V(a.x - b.x,a.y - b.y);}
V operator * (V a,double k){return V(a.x*k,a.y*k);}
V operator / (V a,double k){return V(a.x/k,a.y/k);}
double operator * (V a,V b){return (a.x * b.y) - (a.y * b.x);};
double touying(V a,V b){ //求 b 在 a 上的投影
double S = fabs(a * b) / 2;
double h = S / a.len * 2;
return sqrt(b.len * b.len - h * h);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1; i<=n; i++){
a[i].get_len();
}
for(int i=1; i<=m; i++){
int opt;
scanf("%d",&opt);
if(opt == 1){
int x,y;
scanf("%d%d",&x,&y);
double ans = 0;
for(int j=x; j<=y; j++){
int now = j;
int nxt = (j == n ? 1 : j + 1);
ans += touying(a[now],a[nxt]) * a[now].len / 2;
}
printf("%.5f\n",ans);
}
else if(opt == 2){
int now;
double k;
scanf("%d%lf",&now,&k);
int nxt = (now == n) ? 1 : now + 1;
V he = a[now] + a[nxt];
double len = a[now].len;
a[now] = a[now] / len * (len + k);
a[nxt] = he - a[now];
a[now].get_len();a[nxt].get_len();
}
}
return 0;
}
在写出 的暴力之后，正解已经呼之欲出了——区间求和，单点修改，显然可以用线段树维护 。
对于 操作，直接求和即可。
对于 操作，这里有些坑点。题目中全程只提到了 和 的变化，但是只变这两个吗？答案是否定的。考虑到 是与向量 有关的，所以当 更改时， 也将会发生变化。
也就是说，对于一次更改，边 和 会同时改变向量和 ，边 只会改变 。这里对 改变的话还需要访问 ，所以我们还要再加一个特判。
这样，每次 操作我们需要单点更新 次。
这里我的写法是 ，这样做还需要将线段树的建树范围从 更改到 。
这样我们就可以用 的时间复杂度下解决了。
double gog(double a, double b)
{
return sqrt(a * a + b * b);
}
int main()
{
kkk[n + 1] = kkk[1];
kkk[n + 2] = kkk[2];
int nn = n + 2;
build(1, 1, nn);
while(m--)
{
int opt, l, r;
scanf("%d%d%d", &opt, &l, &r);
if(opt == 1)
{
printf("%.6lf\n", query(1, l, r) / 2.00);
}
else
{
np ver1 = mp((gog(kkk[l].fi, kkk[l].se) + r) / gog(kkk[l].fi, kkk[l].se) * kkk[l].fi, (gog(kkk[l].fi, kkk[l].se) + r) / gog(kkk[l].fi, kkk[l].se) * kkk[l].se);
np ver2 = mp(kkk[l].fi + kkk[l + 1].fi, kkk[l].se + kkk[l + 1].se);
np ver3 = mp(ver2.fi - ver1.fi, ver2.se - ver1.se);
kkk[l] = ver1;
kkk[l + 1] = ver3;
if(l == 1) kkk[n + 1] = ver1;
if(l == n) kkk[1] = ver3;
update(1, l, abs(kkk[l + 1].fi * kkk[l].fi + kkk[l + 1].se * kkk[l].se));
update(1, l + 1, abs(kkk[l + 2].fi * kkk[l + 1].fi + kkk[l + 2].se * kkk[l + 1].se));
if(l == 1)
{
update(1, n, abs(kkk[n].fi * kkk[1].fi + kkk[n].se * kkk[1].se));
continue;
}
update(1, l - 1, abs(kkk[l - 1].fi * kkk[l].fi + kkk[l - 1].se * kkk[l].se));
}
}
return 0;
}
细节还是很多的，建议自己上手写写。