Cod sursa(job #1385030)

Utilizator SmarandaMaria Pandele Smaranda Data 11 martie 2015 17:18:36
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <cstdio>
#include <cfloat>
#include <algorithm>

using namespace std;

const int N = 303;
const double eps = 1.e-14;

struct Point {
    int x, y;
};

Point P [N];
int n, p, dp [N][N], v1 [N], v2 [N];
double arie1 [N], arie2 [N], arie [N];

int ccw (const Point &A, const Point &B, const Point &C) {
    int cp;

    cp = (A.x - C.x) * (B.y - C.y) - (A.y - C.y) * (B.x - C.x);
    return cp;
}

bool PointUnderSegment (const Point &A, const Point &B, const Point &C) {
    int cp, x1, x2;

    if (A.x < B.x || (A.x == B.x && A.y < B.y))
        cp = ccw (A, B, C);
    else cp = ccw (B, A, C);
    if (cp >= 0)
        return 0;
    x1 = min (A.x, B.x);
    x2 = A.x + B.x - x1;
    if (C.x > x1 && C.x <= x2)
        return 1;
    return 0;
}

void precompute () {
    int i, j, k;

    for (i = 1; i <= n; i ++)
        for (j = i + 1; j <= n; j ++) {
            dp [i][j] = dp [j][i] = 0;
            for (k = 1; k <= n; k ++)
                if (PointUnderSegment (P [i], P [j], P [k])) {
                    dp [i][j] ++;
                    dp [j][i] ++;
                }
        }
}

int compute (const int &a, const int &b, const int &c) {
    int cp;

   if (P [a].x < P [b].x || (P [a].x == P [b].x && P [a].y < P [b].y))
        cp = ccw (P [a], P [b], P [c]);
    else cp = ccw (P [b], P [a], P [c]);
    if (cp == 0)
        return 0;
    if (cp > 0)
        return -dp [a][b];
    else
        if (PointUnderSegment (P [a], P [b], P [c]))
            return dp [a][b] - 1;
        else return dp [a][b];
}

int solve (const int &a, const int &b, const int &c) {
    int ans = 0;

    ans = ans + compute (a, b, c);
    ans = ans + compute (a, c, b);
    ans = ans + compute (b, c, a);
    return ans;
}

int main () {
    int i, j, cp, k, lim;
    double ans, S;

    freopen ("popandai.in", "r", stdin);
    freopen ("popandai.out", "w", stdout);

    scanf ("%d%d", &n, &p);
    for (i = 1; i <= n; i ++)
        scanf ("%d%d", &P [i].x, &P [i].y);

    precompute ();

    ans = DBL_MAX;
    for (i = 1; i <= n; i ++)
        for (j = i + 1; j <= n; j ++) { // diagonala
            v1 [0] = v2 [0] = 0;
            for (k = 0; k <= n; k ++)
                arie [k] =DBL_MAX;
            for (k = 1; k <= n; k ++)
                if (i != k && k != j) {
                    cp = ccw (P [i], P [j], P [k]);
                    if (cp == 0)
                        continue;
                    if (cp < 0) {
                        v1 [++ v1 [0]] = solve (i, j, k);
                        arie1 [v1 [0]] = 0.5 * cp * -1;
                    }
                    else {
                         v2 [++ v2 [0]] = solve (i, j, k);
                         arie2 [v2 [0]] = 0.5 * cp;
                    }
                }
            lim = 0;
            for (k = 1; k <= v1 [0]; k ++) {
                arie [v1 [k]] = min (arie [v1 [k]], arie1 [k]);
                if (v1 [k] > lim)
                    lim = v1 [k];
            }
            for (k = lim - 1; k >= 1; k --)
                arie [k] = min (arie [k], arie [k + 1]);
            for (k = 1; k <= v2 [0]; k ++) {
                lim = p - v2 [k];
                if (lim < 0)
                    lim = 0;
                S = arie2 [k] + arie [lim];
                if (S - ans <= -eps)
                    ans = S;
            }
        }
    printf ("%lf", ans);
    return 0;
}