poj3200

题意：给出一些圆盘，质量和面积成正比，把他们一层一层的按照规定的坐标罗起来，问到哪一层会不稳定。不稳定的意思就是说中间存在某一个圆盘，它上面的所有圆盘的质心在它的面积范围之外。题目对输出中的哪一层的k描述有误，实际输出的层号比题中描述的小1。

分析：利用质心公式

X=(X1*M1+X2*M2+ ... ... +Xn*Mn)/(M1+M2+ ... ... +Mn) ,
Y=(Y1*M1+Y2*M2+......+Yn*Mn)/(M1+M2+......+Mn)

用n^2的效率判断即可。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;

#define maxn 1005

struct Elem
{
    long long x, y, r;
} block[maxn];

int n;

void input()
{
    for (int i = 0; i < n; i++)
        scanf("%lld%lld%lld", &block[i].x, &block[i].y, &block[i].r);
}

bool unstable(Elem a, Elem b, Elem c)
{
    double bx = b.x * 1.0 / c.x;
    double by = b.y * 1.0 / c.y;
    double xx = a.x - bx;
    double yy = a.y - by;
    return xx * xx + yy * yy >= a.r * a.r;
}

int main()
{
    //freopen("t.txt", "r", stdin);
    while (scanf("%d", &n), n)
    {
        input();
        bool ok = true;
        for (int i = 1; i < n; i++)
        {
            Elem b, c;
            b.x = b.y = 0;
            c.x = c.y = 0;
            for (int j = i; j > 0; j--)
            {
                b.x += block[j].x * block[j].r * block[j].r;
                c.x += block[j].r * block[j].r;
                b.y += block[j].y * block[j].r * block[j].r;
                c.y += block[j].r * block[j].r;
                if (unstable(block[j - 1], b, c))
                {
                    printf("Unfeasible %d\n", i);
                    ok = false;
                    break;
                }
            }
            if (!ok)
                break;
        }
        if (ok)
            printf("Feasible\n");
    }
    return 0;
}