BZOJ2508 简单题

2015.01.07 19:53 Wed| 7 visits oi_2015| 2015_刷题日常| Text

Solution

嗯,真是一个简单题呢~

//RE到死发现数组开小,特判的时候改错地方,外加各种脑残不脑残的错误的简单题 T^T

说起来倒是好听,简简单单地用拉格朗日乘数法化简,得到一个只关于 x 和 y 的方程组,解出 x 和 y 后带回原函数即得最小值。只不过,过程中得到的解很可能为 0 ,答案中就会出现可爱的 nan ……

于是需要加上各种丧病地特判。

下面附上第一个测试点 >.<

Data1.in:
    25
    0 0 0 1 0
    2
    0 0 1 1 1
    2
    0 0 2 1 2
    2
    1 1
    1 2
    1 3
    0 0 0 0 1
    2
    0 1 0 1 1
    2
    0 2 0 2 1
    2
    1 4
    1 5
    1 6
    0 0 0 1 1
    0 1 0 2 1
    2
    0 2 0 3 1
    2
    0 0 0 -1 1
    2

Data1.out:
    0.00
    0.50
    2.00
    0.00
    0.50
    2.00
    0.25
    1.00
    1.00

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define eps 1e-10
#define sqr(x) ((x)*(x))

struct line
{
    double a, b, c, s;
    line() {}
    line(double _a, double _b, double _c): a(_a), b(_b), c(_c)
    { s = sqr(a) + sqr(b); }
};

line l[N];
int n, opt, t;
double a, b, c, d, e, f;

int main()
{
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        scanf("%d", &opt);
        if (opt == 0)
        {
            double x0, y0, x1, y1;
            scanf("%lf%lf%lf%lf", &x0, &y0, &x1, &y1);
            l[++t] = line(y1-y0, x0-x1, x1*y0-x0*y1);
            a += sqr(l[t].a) / l[t].s;
            b += sqr(l[t].b) / l[t].s;
            c += sqr(l[t].c) / l[t].s;
            d += 2 * l[t].a * l[t].b / l[t].s;
            e += 2 * l[t].a * l[t].c / l[t].s;
            f += 2 * l[t].b * l[t].c / l[t].s;
        }
        else if (opt == 1)
        {
            int x; scanf("%d", &x);
            a -= sqr(l[x].a) / l[x].s;
            b -= sqr(l[x].b) / l[x].s;
            c -= sqr(l[x].c) / l[x].s;
            d -= 2 * l[x].a * l[x].b / l[x].s;
            e -= 2 * l[x].a * l[x].c / l[x].s;
            f -= 2 * l[x].b * l[x].c / l[x].s;
        }
        else
        {
            double x, y;
            double p = 4 * a * b - sqr(d);
            if (fabs(p) < eps)
            {
                if (fabs(d) < eps) {
                    if (fabs(a) > eps) x = -e/(2*a), y = 0;
                    else if (fabs(b) > eps) x = 0, y = -f/(2*b);
                    else { puts("0.00"); continue; }
                }
                else x = -e/(2*a), y = 0;
            }
            else x = (d*f - 2*b*e)/p, y = (d*e - 2*a*f)/p;
            printf("%.2lf\n", a*sqr(x) + b*sqr(y) + c + d*x*y + e*x + f*y);
        }
    }
}