CF38D Vasya the Architect 题解

· · 题解

前言

CF 远古物理题，没给出任何的提示，对于一些物理不好的同学不是很公平。而且官网上只有俄语题解。

解法

本题需要一些前置物理知识。

一个物体是稳定的，当且仅当在它的任何点上，施加在该点上的力矩和为零。即，该物体的质心投影位于该物体所在的支点投影的内部或边界时，它才是稳定的。

考虑原问题，每次添加一个立方体时，都要考虑它会不会使整个系统的稳定的状态被打破：只用判断整个“塔”中的所有“后缀”是否稳定即可。具体地，我们只要求出这个后缀的质心即可解决问题。

按照题目描述，设整个“后缀”的质心投影的坐标为 (x_c,y_c)，每一个立方体的投影的左上角、右下角的坐标为 (x_{i,1},y_{i,1}),(x_{i,2},y_{i,2})，我们有：

设 x_i=\dfrac{x_{i,1}+x_{i,2}}{2},y_i=\dfrac{y_{i,1}+y_{i,2}}{2},

m_i=|x_{i,1}-x_{i,2}|^3=|y_{i,1}-y_{i,2}|^3,

有 x_c=\dfrac{\sum\limits_im_ix_i}{\sum\limits_im_i},y_c=\dfrac{\sum\limits_im_iy_i}{\sum\limits_im_i}。

直接套用上面的公式循环求解即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> a(n),b(n),c(n);
  for(int i=0;i<n;i++){
    int x1,y_,x2,y2; cin>>x1>>y_>>x2>>y2;
    // 这里不用 y1 的原因是会与 cmath 库里面的 y1 函数发生命名冲突，导致 CE
    a[i]=x1+x2,b[i]=y_+y2,c[i]=abs(x2-x1); // c[i] 的立方即为 m[i]
    for(int j=0;j<i;j++){
      double u=0,v=0; int w=0;
      for(int k=j+1;k<=i;k++){
        int m=c[k]*c[k]*c[k];
        u+=a[k]*m,v+=b[k]*m,w+=m; // 套公式
      }
      u=u/w,v=v/w; // 套公式，两个和相除
      if(max(fabs(u-a[j]),fabs(v-b[j]))>c[j]+1e-8){
        cout<<i<<endl; return 0;
      } // 判断质心的投影是否在规定区域内，加上 1e-8 是为了避免精度误差
    }
  }
  cout<<n<<endl; // 能垒完所有的立方体
  return 0;
}