team2012-F3-sol-0004

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给定4个圆的圆心且限制4个圆无公共部分相交，求半径之和的最大值。
是一个线性规划问题：
最大化：x1 + x2 + x3 + x4
约束：  x1 + x2 <= a1, x1 + x3 <= a2...共6个约束，且x1, x2, x3, x4 >= 0
即可以用单纯形算法解决。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const double INFI = 1e20;
double mat[100][100];
int n, m, x[10], y[10];

double gao()
{
    while(true)
    {
        int find = 0, col, row;

        for(int i=1;i<=n;i++)
            if(mat[m+1][i] > 0)
            {
                find = 1;
                col = i;
                break;
            }
        if(!find)   return mat[m+1][n+1];

        double min_i = INFI;
        for(int i=1;i<=m;i++)
            if(mat[i][col] > 0)
            {
                double t = mat[i][n+1]/mat[i][col];
                if(min_i > t)
                {
                    min_i = t;
                    row = i;
                }
            }

        double tmp = mat[row][col];
        for(int i=1;i<=n+1;i++)
            mat[row][i] /= tmp;
        mat[row][col] = 1/tmp;

        for(int i=1;i<=m+1;i++)
            if(row!=i)
            {
                for(int j=1;j<=n;j++)
                    if(col!=j)
                        mat[i][j] -= mat[i][col]*mat[row][j];
                if(i==m+1)
                    mat[i][n+1] += mat[i][col]*mat[row][n+1];
                else
                    mat[i][n+1] -= mat[i][col]*mat[row][n+1];
                mat[i][col] = (-1)*mat[i][col]*mat[row][col];
            }
    }
}

double dis(int i, int j)
{
    double dx = x[i]-x[j],
           dy = y[i]-y[j];
    return sqrt(dx*dx+dy*dy);
}

int main()
{
    while(cin>>x[1]>>y[1])
    {
        for(int i=2;i<=4;i++)
            cin>>x[i]>>y[i];
        m = 0;
        n = 4;

        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                m++;
                for(int k=1;k<=n;k++)
                    if(k==i || k==j)
                        mat[m][k] = 1;
                    else
                        mat[m][k] = 0;
                mat[m][n+1] = dis(i, j);
            }
        for(int i=1;i<=n;i++)
            mat[m+1][i] = 1;
        mat[m+1][n+1] = 0;

        cout.precision(8);
        cout<<fixed<<gao()<<endl;
    }

    return 0;
}
}}}

题意：给定4个圆的圆心且限制4个圆无公共部分相交，求半径之和的最大值。
是一个线性规划问题：
最大化：x1 + x2 + x3 + x4
约束：  x1 + x2 <= a1, x1 + x3 <= a2...共6个约束，且x1, x2, x3, x4 >= 0
即可以用单纯形算法解决。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double INFI = 1e20;
double mat[100][100];
int n, m, x[10], y[10];
double gao()
{
    while(true)
    {
        int find = 0, col, row;
        for(int i=1;i<=n;i++)
            if(mat[m+1][i] > 0)
            {
                find = 1;
                col = i;
                break;
            }
        if(!find)   return mat[m+1][n+1];
        double min_i = INFI;
        for(int i=1;i<=m;i++)
            if(mat[i][col] > 0)
            {
                double t = mat[i][n+1]/mat[i][col];
                if(min_i > t)
                {
                    min_i = t;
                    row = i;
                }
            }
        double tmp = mat[row][col];
        for(int i=1;i<=n+1;i++)
            mat[row][i] /= tmp;
        mat[row][col] = 1/tmp;
        for(int i=1;i<=m+1;i++)
            if(row!=i)
            {
                for(int j=1;j<=n;j++)
                    if(col!=j)
                        mat[i][j] -= mat[i][col]*mat[row][j];
                if(i==m+1)
                    mat[i][n+1] += mat[i][col]*mat[row][n+1];
                else
                    mat[i][n+1] -= mat[i][col]*mat[row][n+1];
                mat[i][col] = (-1)*mat[i][col]*mat[row][col];
            }
    }
}
double dis(int i, int j)
{
    double dx = x[i]-x[j],
           dy = y[i]-y[j];
    return sqrt(dx*dx+dy*dy);
}
int main()
{
    while(cin>>x[1]>>y[1])
    {
        for(int i=2;i<=4;i++)
            cin>>x[i]>>y[i];
        m = 0;
        n = 4;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                m++;
                for(int k=1;k<=n;k++)
                    if(k==i || k==j)
                        mat[m][k] = 1;
                    else
                        mat[m][k] = 0;
                mat[m][n+1] = dis(i, j);
            }
        for(int i=1;i<=n;i++)
            mat[m+1][i] = 1;
        mat[m+1][n+1] = 0;
        cout.precision(8);
        cout<<fixed<<gao()<<endl;
    }
    return 0;
}