130804組隊練習賽ZOJ校賽

A.Ribbon Gymnastics

題目要求四個點作圓，且圓與圓之間不能相交的半徑之和的最大值。我當時想法很簡單，只要兩圓相切，它們的半徑之和一定最大，但是要保證不能相交的話就只能取兩兩個點間距離和最短的作為半徑和最大的。到現在也不是非常清楚為什麼可以A，我們帶錯節奏了。。

[cpp] 
#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<cmath>  
#define exp 1e-10  
using namespace std; 
inline void RD(int &ret) 
{ 
    char c; 
    do 
    { 
        c=getchar(); 
    } 
    while(c<'0'||c>'9'); 
    ret=c-'0'; 
    while((c=getchar())>='0'&&c<='9') 
    { 
        ret=ret*10+(c-'0'); 
    } 
} 
inline void OT(int a) 
{ 
    if(a>=10) 
    { 
        OT(a/10); 
    } 
    putchar(a%10+'0'); 
} 
double x[4],y[4]; 
double getdis(int i ,int j) 
{ 
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); 
} 
int main() 
{ 
    int i; 
    double s1,s2,s3; 
    while(scanf("%lf%lf",&x[0],&y[0])!=EOF) 
    { 
        for(i=1; i<4; i++) 
        { 
            scanf("%lf%lf",&x[i],&y[i]); 
        } 
        s1=getdis(0,1)+getdis(2,3); 
        s2=getdis(1,2)+getdis(0,3); 
        s3=getdis(0,2)+getdis(1,3); 
        printf("%.6f\n",min(s1,min(s2,s3))); 
    } 
    return 0 ; 
} 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define exp 1e-10
using namespace std;
inline void RD(int &ret)
{
    char c;
    do
    {
        c=getchar();
    }
    while(c<'0'||c>'9');
    ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    {
        ret=ret*10+(c-'0');
    }
}
inline void OT(int a)
{
    if(a>=10)
    {
        OT(a/10);
    }
    putchar(a%10+'0');
}
double x[4],y[4];
double getdis(int i ,int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
    int i;
    double s1,s2,s3;
    while(scanf("%lf%lf",&x[0],&y[0])!=EOF)
    {
        for(i=1; i<4; i++)
        {
            scanf("%lf%lf",&x[i],&y[i]);
        }
        s1=getdis(0,1)+getdis(2,3);
        s2=getdis(1,2)+getdis(0,3);
        s3=getdis(0,2)+getdis(1,3);
        printf("%.6f\n",min(s1,min(s2,s3)));
    }
    return 0 ;
}

E.Magnet Darts
一道計算幾何題，計算落在距離要求點一個單位正方形范圍內的點都需要得到一個分數，求期望。由於讀錯題意，想太復雜了。。。

我們可以枚舉矩形內的所有整點，判斷整點是否在要求的多邊形內或邊緣，計算整點周圍區域面積乘以分數，相加求和，再與平面總面積相除，求期望。

[cpp] 
#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<cmath>  
#define exp 1e-10  
using namespace std; 
inline void RD(int &ret) 
{ 
    char c; 
    do 
    { 
        c=getchar(); 
    } 
    while(c<'0'||c>'9'); 
    ret=c-'0'; 
    while((c=getchar())>='0'&&c<='9') 
    { 
        ret=ret*10+(c-'0'); 
    } 
} 
inline void OT(int a) 
{ 
    if(a>=10) 
    { 
        OT(a/10); 
    } 
    putchar(a%10+'0'); 
} 
struct xl 
{ 
    double x,y; 
}p[22]; 
int n; 
int f2(double x)//判斷是否為零  
{ 
    if(fabs(x)<exp) 
    { 
        return 0; 
    } 
    else 
    { 
        if(x<0) 
        { 
            return -1; 
        } 
        else 
        { 
            return 1; 
        } 
    } 
} 
double f1(xl p1,xl p2,xl p0)//判斷邊緣  
{ 
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 
} 
double f3(xl p1,xl p2,xl p0)//判斷內部  
{ 
    return (p1.x-p0.x)*(p2.x-p0.x)+(p2.y-p0.y)*(p1.y-p0.y); 
} 
bool f(xl z) 
{ 
    int i,j=0; 
    xl p1,p2; 
    for(i=0;i<n;++i) 
    { 
        p1=p[i]; 
        p2=p[(i+1)%n]; 
        if(f2(f1(p1,p2,z))==0&&f2(f3(p1,p2,z))<=0) 
        { 
            return true; 
        } 
        if(f2(f1(p2,z,p1))>0&&f2(p1.y-z.y)<=0&&f2(p2.y-z.y)>0) 
        { 
            j++; 
        } 
        if(f2(f1(p2,z,p1))<0&&f2(p1.y-z.y)>0&&f2(p2.y-z.y)<=0) 
        { 
            j--; 
        } 
    } 
    if(j!=0) 
    { 
        return true; 
    } 
    else 
    { 
        return false; 
    } 
} 
int main() 
{ 
    xl a,b,z; 
    int i,j; 
    double sum,ans,lx,ly,hx,hy,A,B; 
    while(scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y)!=EOF) 
    { 
        RD(n); 
        scanf("%lf%lf",&A,&B); 
        for(i=0;i<n;++i) 
        { 
            scanf("%lf%lf",&p[i].x,&p[i].y); 
        } 
        sum=(a.x-b.x)*(a.y-b.y); 
        ans=0.0; 
        for(i=a.x;i<=b.x;++i) 
        { 
            for(j=a.y;j<=b.y;++j) 
            { 
                z.x=i; 
                z.y=j; 
                if(f(z)==true)//求區域面積分數  
                { 
                    lx=max(i-0.5,a.x); 
                    ly=max(j-0.5,a.y); 
                    hx=min(i+0.5,b.x); 
                    hy=min(j+0.5,b.y); 
                    ans+=(hx-lx)*(hy-ly)*(A*i+B*j); 
                } 
            } 
        } 
        printf("%.3f\n",ans/sum); 
    } 
    return 0; 
} 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define exp 1e-10
using namespace std;
inline void RD(int &ret)
{
    char c;
    do
    {
        c=getchar();
    }
    while(c<'0'||c>'9');
    ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    {
        ret=ret*10+(c-'0');
    }
}
inline void OT(int a)
{
    if(a>=10)
    {
        OT(a/10);
    }
    putchar(a%10+'0');
}
struct xl
{
    double x,y;
}p[22];
int n;
int f2(double x)//判斷是否為零
{
    if(fabs(x)<exp)
    {
        return 0;
    }
    else
    {
        if(x<0)
        {
            return -1;
        }
        else
        {
            return 1;
        }
    }
}
double f1(xl p1,xl p2,xl p0)//判斷邊緣
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double f3(xl p1,xl p2,xl p0)//判斷內部
{
    return (p1.x-p0.x)*(p2.x-p0.x)+(p2.y-p0.y)*(p1.y-p0.y);
}
bool f(xl z)
{
    int i,j=0;
    xl p1,p2;
    for(i=0;i<n;++i)
    {
        p1=p[i];
        p2=p[(i+1)%n];
        if(f2(f1(p1,p2,z))==0&&f2(f3(p1,p2,z))<=0)
        {
            return true;
        }
        if(f2(f1(p2,z,p1))>0&&f2(p1.y-z.y)<=0&&f2(p2.y-z.y)>0)
        {
            j++;
        }
        if(f2(f1(p2,z,p1))<0&&f2(p1.y-z.y)>0&&f2(p2.y-z.y)<=0)
        {
            j--;
        }
    }
    if(j!=0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    xl a,b,z;
    int i,j;
    double sum,ans,lx,ly,hx,hy,A,B;
    while(scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y)!=EOF)
    {
        RD(n);
        scanf("%lf%lf",&A,&B);
        for(i=0;i<n;++i)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        sum=(a.x-b.x)*(a.y-b.y);
        ans=0.0;
        for(i=a.x;i<=b.x;++i)
        {
            for(j=a.y;j<=b.y;++j)
            {
                z.x=i;
                z.y=j;
                if(f(z)==true)//求區域面積分數
                {
                    lx=max(i-0.5,a.x);
                    ly=max(j-0.5,a.y);
                    hx=min(i+0.5,b.x);
                    hy=min(j+0.5,b.y);
                    ans+=(hx-lx)*(hy-ly)*(A*i+B*j);
                }
            }
        }
        printf("%.3f\n",ans/sum);
    }
    return 0;
}
F.Final Exam Arrangement

一道水貪心，找到相應區間標記下就行了。

[cpp] 
#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<cmath>  
#define exp 1e-10  
using namespace std; 
inline void RD(int &ret) 
{ 
    char c; 
    do 
    { 
        c=getchar(); 
    } 
    while(c<'0'||c>'9'); 
    ret=c-'0'; 
    while((c=getchar())>='0'&&c<='9') 
    { 
        ret=ret*10+(c-'0'); 
    } 
} 
inline void OT(int a) 
{ 
    if(a>=10) 
    { 
        OT(a/10); 
    } 
    putchar(a%10+'0'); 
} 
struct xl 
{ 
    int x,y,id; 
} s[100001]; 
bool cmp(xl x,xl y)//結構體排序  
{ 
    if(x.x==y.x) 
    { 
        return x.y<y.y; 
    } 
    return x.x<y.x; 
} 
int main() 
{ 
    int i,n,j,r; 
    bool v[100001]; 
    while(scanf("%d",&n)!=EOF) 
    { 
        for(i=0; i<n; ++i) 
        { 
            RD(s[i].x); 
            RD(s[i].y); 
            s[i].id=i+1; 
        } 
        sort(s,s+n,cmp); 
        j=0; 
        r=-1; 
        for(i=0; i<n; ++i) 
        { 
            v[i]=false;//標記  
            if(s[i].x>=r) 
            { 
                r=s[i].y; 
                j++; 
                v[i]=true; 
            } 
            r=min(r,s[i].y); 
        } 
        OT(j); 
        for(i=0; i<n; ++i) 
        { 
            if(v[i]) 
            { 
                printf("\n"); 
                OT(s[i].id); 
            } 
            else 
            { 
                printf(" "); 
                OT(s[i].id); 
            } 
        } 
        printf("\n\n"); 
    } 
    return 0; 
} 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define exp 1e-10
using namespace std;
inline void RD(int &ret)
{
    char c;
    do
    {
        c=getchar();
    }
    while(c<'0'||c>'9');
    ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    {
        ret=ret*10+(c-'0');
    }
}
inline void OT(int a)
{
    if(a>=10)
    {
        OT(a/10);
    }
    putchar(a%10+'0');
}
struct xl
{
    int x,y,id;
} s[100001];
bool cmp(xl x,xl y)//結構體排序
{
    if(x.x==y.x)
    {
        return x.y<y.y;
    }
    return x.x<y.x;
}
int main()
{
    int i,n,j,r;
    bool v[100001];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0; i<n; ++i)
        {
            RD(s[i].x);
            RD(s[i].y);
            s[i].id=i+1;
        }
        sort(s,s+n,cmp);
        j=0;
        r=-1;
        for(i=0; i<n; ++i)
        {
            v[i]=false;//標記
            if(s[i].x>=r)
            {
                r=s[i].y;
                j++;
                v[i]=true;
            }
            r=min(r,s[i].y);
        }
        OT(j);
        for(i=0; i<n; ++i)
        {
            if(v[i])
            {
                printf("\n");
                OT(s[i].id);
            }
            else
            {
                printf(" ");
                OT(s[i].id);
            }
        }
        printf("\n\n");
    }
    return 0;
}
J.Painting Storages

一道排列組合的題目，需要找到狀態分解：

當dp[i-1]已經滿足狀況了：dp[i]=dp[i-1]*2；

當dp[i-1]還沒滿足狀況，則[i-m+1,i]區間則用來滿足條件，則i-m必為藍色，所以dp[i-m-1]不能包括在內。所以需要dp[i-1]+pow(2,i-m-1)-dp[i-m-1]；

[cpp] 
#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<cmath>  
#define N 1000000007  
using namespace std; 
inline void RD(int &ret) 
{ 
    char c; 
    do 
    { 
        c=getchar(); 
    } 
    while(c<'0'||c>'9'); 
    ret=c-'0'; 
    while((c=getchar())>='0'&&c<='9') 
    { 
        ret=ret*10+(c-'0'); 
    } 
} 
inline void OT(int a) 
{ 
    if(a>=10) 
    { 
        OT(a/10); 
    } 
    putchar(a%10+'0'); 
} 
long long dp[100001],a[100001]; 
void f() 
{ 
    a[0]=1; 
    int i; 
    for(i=1; i<100001; ++i)//構造2次冪表  
    { 
        a[i]=a[i-1]*2%N; 
    } 
} 
int main() 
{ 
    f(); 
    int i,n,m; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        memset(dp,0,sizeof(dp)); 
        dp[m]=1; 
        for(i=m+1; i<=n; ++i) 
        { 
            dp[i]=((dp[i-1]*2%N+a[i-m-1])%N-dp[i-m-1]+N)%N;//狀態遞推過程  
        } 
        cout<<dp[n]<<endl; 
    } 
    return 0 ; 
} 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
    char c;
    do
    {
        c=getchar();
    }
    while(c<'0'||c>'9');
    ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    {
        ret=ret*10+(c-'0');
    }
}
inline void OT(int a)
{
    if(a>=10)
    {
        OT(a/10);
    }
    putchar(a%10+'0');
}
long long dp[100001],a[100001];
void f()
{
    a[0]=1;
    int i;
    for(i=1; i<100001; ++i)//構造2次冪表
    {
        a[i]=a[i-1]*2%N;
    }
}
int main()
{
    f();
    int i,n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        dp[m]=1;
        for(i=m+1; i<=n; ++i)
        {
            dp[i]=((dp[i-1]*2%N+a[i-m-1])%N-dp[i-m-1]+N)%N;//狀態遞推過程
        }
        cout<<dp[n]<<endl;
    }
    return 0 ;
}