luogu P4515 [COCI2009-2010#6] XOR-白红宇

luogu P4515 [COCI2009-2010#6] XOR

阅读量：6281 次

发布时间：2019-06-22

本文共 1775 字，大约阅读时间需要 5 分钟。

描述

坐标系下有若干个等腰直角三角形，且每个等腰直角三角形的直角顶点都在左下方，两腰与坐标轴平行。被奇数个三角形覆盖的面

积部分为灰色，被偶数个三角形覆盖的面积部分为白色，如下图所示。

已知 NN个等腰直角三角形的顶点坐标及腰长，求灰色部分面积。

输入输出格式

输入格式：

输入第一行包含一个整数 NN，表示等腰直角三角形数量。

接下来 NN行，每行三个整数 X, Y, RX,Y,R，分别表示等腰直角三角形的顶点坐标 (X, Y)(X,Y)与腰长 RR。

输入输出样例

输入样例#1： 复制

31 1 27 1 65 3 4

输出样例#1：

24.0

这是自己做出的第一道容斥题（除了一些SB容斥），虽然这道题也不算太难，而且我做了一个晚上。总之就是自己在容斥上还是太菜了。

还是来说题吧。首先要会求多个三角形的交。显然这道题中两个等腰直角的交还是一个等腰直角三角形。我的做法是分类讨论，不如洛谷上题解那么简洁，于是就不说了。

重点是算出容斥系数。我们设 $i$ 个三角形的交的容斥系数为 $f[i]$ 。显然 $f[1]=1$ 。对于 $i>1$ ，的情况，我们先设初值，显然如果 $i$ 为奇数，那么初值为1，否则为0。然后我们要容斥去重。 $f[i]-=\sum _{1<=j<i}C_{i}^{j}*f[j]$ 。计算 $j$ 个三角形的交的时候， $i$ 个三角形的交会被计算 $C_{i}^{j}$ 次。

然后通过观察证明可以知道 $f[i]=(-1)^{i+1}\cdot 2^{i-1}$ 。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #define ll long long#define N 11using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n;ll ans;ll f[N];ll c[N][N];struct tri {ll x,y,r;}s[N],tem,g;void work(tri a,tri b) { if(a.y>b.y) swap(a,b); if(a.x<=b.x) { int r=min(b.r,a.r-(b.x+b.y-a.x-a.y)); if(r<0) return g.r=-1,void(); g=b; g.r=r; } else { int r=min(a.y+a.r-b.y,b.x+b.r-a.x); if(r<0) return g.r=-1,void(); g.x=a.x,g.y=b.y; g.r=r; }}void dfs(int v,ll x,ll y,ll r,int tot) { if(r<=0&&tot) return ; if(v>n) { if(!tot) return ; ans+=r*r*f[tot]; return ; } dfs(v+1,x,y,r,tot); if(!tot) { dfs(v+1,s[v].x,s[v].y,s[v].r,tot+1); } else { tem.x=x,tem.y=y,tem.r=r; work(s[v],tem); dfs(v+1,g.x,g.y,g.r,tot+1); }}int main() { n=Get(); c[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=i;j++) { c[i][j]=(!j||i==j)?1:c[i-1][j-1]+c[i-1][j]; } } for(int i=1;i<=n;i++) { f[i]=(i&1)?1:0; for(int j=1;j

转载于:https://www.cnblogs.com/hchhch233/p/9735817.html

你可能感兴趣的文章