[CF379E](New Year Tree Decorations)

• 題意

給你一堆坐标軸上的多邊形,它們互相覆寫,求每個多邊形露出部分的面積

• solution

正解(計算幾何)是不可能會的

有一種神奇的方法

用類似于定積分的思想去做

把每條邊劃分成很小很小的段,

對于每段用矩形去近似覆寫

即每段面積計算為左邊線段長度乘以寬度

玄學

• code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2000000;
int n,k,m;
long double height,h1,h2,ans,plk;
long double front[M+1];
int main(){
   scanf("%d%d",&n,&k);
   m=M/k;
   for(int i=1;i<=n;i++){
     ans=0.0;
     scanf("%Lf",&h1);
     for(int r=1;r<=k;r++){
        scanf("%Lf",&h2);//h1~h2代表一條線段
        plk=(h2-h1)/m;// plk 即斜率
        for(int p=0;p<m;p++){
           height=h1+plk*p; //目前點的y值
           if(height>front[(r-1)*m+p]){//front 即目前x坐标對應的最高節點,如果目前節點比它還高那麼這段面積就是露在外面的,統計答案并更新front
             ans+=height-front[(r-1)*m+p]; //面積公式(由于寬度等于1,就不乘寬度了)
             front[(r-1)*m+p]=height;
             }
           }
         h1=h2;
         }
   cout<<ans/m;
   putchar('\n');
   }
}
           

轉載于:https://www.cnblogs.com/stepsys/p/10383829.html