Cod sursa(job #1389358)

Utilizator ericptsStavarache Petru Eric ericpts Data 16 martie 2015 10:43:26
Problema Popandai Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <fstream>

using namespace std;

const int MAX_N = 300 + 1;
const int INF = (1 << 30) - 1;

struct point {
    int x, y;
};

int n, k;

point v[MAX_N];

int sub[MAX_N][MAX_N];

inline int abs(const int x){
    if(x > 0)
        return x;
    else
        return -x;
}

int cross(const point &A, const point &B, const point &C) {
    const int x1 = B.x - A.x,
              y1 = B.y - A.y,
              x2 = C.x - B.x,
              y2 = C.y - B.y;

    return x1 * y2 - x2 * y1;
}

int area(const int i, const int j, const int k) {
    return abs(cross(v[i], v[j], v[k]));
}

bool right(const point &A, const point &B, const point &C) {
    return cross(A, B, C) < 0;
}

bool left(const point &A, const point &B, const point &C) {
    return cross(A, B, C) > 0;
}

int points(int i, int j, int k) {
    const point A = v[i],
                B = v[j],
                C = v[k];

    if(B.x < A.x)
        return points(j, i, k);
    if(C.x < B.x)
        return points(i, k, j);

    if(left(A, C, B)) {
        return sub[i][j] + sub[j][k] - sub[i][k];
    } else {
        return sub[i][k] - sub[i][j] - sub[j][k];
    }
}

int under[MAX_N];
int over [MAX_N];

unsigned int ans = INF;

void process(const int i, const int j) {
    for(int i = 0 ; i <= n ; ++i)
        under[i] = over[i] = INF;

    for(int k = 1 ; k <= n ; ++k) {
        const int A = area(i, j, k);
        const int inside = points(i, j, k);
        if(left(v[i], v[j], v[k])) {
        //k is over the ij line
            if(A < over[inside])
                over[inside] = A;
        } else if(right(v[i], v[j], v[k])) {
        //k is under the ij line
            if(A < under[inside])
                under[inside] = A;
        }
    }

    for(int i = n - 1 ; i >= 0 ; --i) {
        if(under[i] > under[i + 1])
            under[i] = under[i + 1];
        if(over[i] > over[i + 1])
            over[i] = over[i + 1];
    }

    for(int i = 0 ; i <= k ; ++i) {
        unsigned int now = under[i] + over[k - i];

        if(now < ans)
            ans = now;
    }
}

int main() {
    ifstream in("popandai.in");
    in >> n >> k;
    for(int i = 1 ; i <= n ; ++i) {
        in >> v[i].x >> v[i].y;
    }
    in.close();

    for(int i = 1 ; i <= n ; ++i) {
        for(int j = 1 ; j <= n ; ++j) {
            if(i == j || !(v[i].x < v[j].x))
                continue;
            //i is to the left of j

            for(int k = 1 ; k <= n ; ++k) {
                if(v[i].x <= v[k].x && v[k].x <= v[j].x)
                    sub[i][j] += right(v[i], v[j], v[k]);
            }
            sub[j][i] = sub[i][j];
        }
    }

    for(int i = 1 ; i <= n ; ++i) {
        for(int j = i + 1 ; j <= n ; ++j) {
            process(i, j);
        }
    }

    ofstream out("popandai.out");
    double rez = (double)ans / 2.0;
    out.precision(4);
    out << rez << "\n";
    out.close();

    return 0;
}