Cod sursa(job #1005524)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 5 octombrie 2013 10:53:46
Problema Popandai Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<stdio.h>
#include<algorithm>

#define NMAX 307
#define x first
#define y second
#define LL long long
#define INF 20000000

using namespace std;

int D[NMAX][NMAX], St[NMAX];
int n, K;
LL Ans;
pair<int, int> a[NMAX];

inline int cp(int i, int j, int k)
{
    int Number = (a[j].x - a[i].x) * (a[k].y - a[i].y) - (a[k].x - a[i].x) * (a[j].y - a[i].y);
    return (Number<0?0:1);
}

inline int Aria(int i, int j, int k)
{
    return abs(a[i].x * a[j].y + a[j].x * a[k].y + a[k].x * a[i].y - a[i].x * a[k].y - a[j].x * a[i].y - a[k].x * a[j].y);
}

inline int Nrp(int A, int B, int C){
    if(A > B)
        swap(A, B);
    if(A > C)
        swap(A, C);
    if(B > C)
        swap(B, C);
    if(cp(A, B, C) == 1)
        return D[A][B] + D[B][C] - D[A][C];
    return D[A][C] - D[A][B] - D[B][C] - 1;
}

int main(){
    freopen("popandai.in", "r", stdin);
    freopen("popandai.out", "w", stdout);
    scanf("%d %d", &n, &K);
    for(int i = 1; i <= n; ++ i)
        scanf("%d %d", &a[i].x, &a[i].y);
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++ i)
        for(int j = i + 1; j <= n; ++ j)
            for(int k = i + 1; k <= j; ++ k)
                if(cp(i, k, j) == 0)
                    ++ D[i][j];
    Ans = INF;
    /**for(int i = 1; i <= n; ++ i, printf("\n"))
        for(int j = 1; j <= n; ++ j)
            printf("%d %d = %d\n", i, j, D[i][j]);**/
    for(int i = 1; i <= n; ++ i)
        for(int j = i + 1; j <= n; ++ j){
            for(int k = 0; k <= n + 1; ++ k)
                St[k] = INF;
            for(int k = 1; k <= n; ++ k)
                if(i != k && j != k && cp(i, j, k) == 0){
                    int Puncte = Nrp(i, j, k);
                    St[Puncte] = min(St[Puncte], Aria(i, j, k));
                }
            for(int k = n; k >= 1; -- k)
                St[k] = min(St[k], St[k + 1]);
            for(int k = 1; k <= n; ++ k)
                if(i != k && j != k && cp(i, j, k) == 1){
                    int Puncte = Nrp(i, j, k);
                    int Nr = K - Puncte;
                    if(Nr < 0)
                        Nr = K;
                    if(St[Nr] == INF)
                        continue;
                    Ans = min(Ans, (LL) Aria(i, j, k) + St[Nr]);
                }
        }
    printf("%.1f", (1.0 * Ans) / 2);
    return 0;
}