prow2012-A3-0004

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目要求四个点为圆心，确定每个圆的半径，使每个圆与其他圆无公共部分面积，且半径之和最大.

很裸的线性规划模型，比赛时直接枚举两两组合过了，正确性可以用单纯形证明

{{{
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
double ax[4],ay[4];
double calc(int i,int j){
    return sqrt((ax[i]-ax[j])*(ax[i]-ax[j])+(ay[i]-ay[j])*(ay[i]-ay[j]));
}
int S[100];
double mat[4][4];
int main(){
    int i,j,st,T = 0;
    for (st=0;st<(1<<4);st++){
            int t =0;
            for (i=0;i<4;i++)
                if ((1<<i)&st)
                    t++;
            if (t!=2) continue;
            S[T++] = st;
    }
    while(scanf("%lf%lf",&ax[0],&ay[0])!=EOF){
        for (i=1;i<4;i++)
            scanf("%lf%lf",&ax[i],&ay[i]);
        for (i=0;i<4;i++)
            for (j=i+1;j<4;j++)
                mat[i][j] = mat[j][i] = calc(i,j);
        double ans = 1.0*(1LL<<60);
        for (int k=0;k<T;k++){
            int st = S[k];
            double sum = 0;
            for (i=0;i<4;i++)
                if ((1<<i)&st){
                    for (j=i+1;j<4;j++)
                        if ((1<<j)&st){
                            sum+=mat[i][j];
                        }
                }else {
                    for (j=i+1;j<4;j++)
                        if ((1<<j)&st);
                        else {
                            sum+=mat[i][j];
                        }
                }
            if (sum<ans) ans=sum;
        }
        printf("%.8lf\n",ans);
    }
}

}}}

题目要求四个点为圆心，确定每个圆的半径，使每个圆与其他圆无公共部分面积，且半径之和最大.

很裸的线性规划模型，比赛时直接枚举两两组合过了，正确性可以用单纯形证明

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
double ax[4],ay[4];
double calc(int i,int j){
    return sqrt((ax[i]-ax[j])*(ax[i]-ax[j])+(ay[i]-ay[j])*(ay[i]-ay[j]));
}
int S[100];
double mat[4][4];
int main(){
    int i,j,st,T = 0;
    for (st=0;st<(1<<4);st++){
            int t =0;
            for (i=0;i<4;i++)
                if ((1<<i)&st)
                    t++;
            if (t!=2) continue;
            S[T++] = st;
    }
    while(scanf("%lf%lf",&ax[0],&ay[0])!=EOF){
        for (i=1;i<4;i++)
            scanf("%lf%lf",&ax[i],&ay[i]);
        for (i=0;i<4;i++)
            for (j=i+1;j<4;j++)
                mat[i][j] = mat[j][i] = calc(i,j);
        double ans = 1.0*(1LL<<60);
        for (int k=0;k<T;k++){
            int st = S[k];
            double sum = 0;
            for (i=0;i<4;i++)
                if ((1<<i)&st){
                    for (j=i+1;j<4;j++)
                        if ((1<<j)&st){
                            sum+=mat[i][j];
                        }
                }else {
                    for (j=i+1;j<4;j++)
                        if ((1<<j)&st);
                        else {
                            sum+=mat[i][j];
                        }
                }
            if (sum<ans) ans=sum;
        }
        printf("%.8lf\n",ans);
    }
}